Commonly used operations on linked lists - detailed explanation of reversal

Commonly used operations on linked lists - reversal

Let’s first define a node class for a singly linked list

public class ListNode {2         
int val;3         ListNode next = null;// 指向的下个节点4 5         
ListNode(int val) {6             this.val = val;7         }8     
}

Implement the reversal of a singly linked list There are two methods

1. Use recursion and reverse from back to front. Start from the head node, search backward until you find the tail node, and then start reversing.​

 1     public ListNode reverseList(ListNode head) { 2         
 if (head == null || head.next == null) 3             return head; 4  5         
 ListNode prev = reverseList(head.next);// 递归调用,先反转下个节点 6  7         
 head.next.next = head;// 将当前结点的指针域指向前一结点 8         
 head.next = null;// 前一结点的指针域令为null; 9         
 return prev;// 反转后新链表的头结点10     
 }

2. Use traversal and reverse from front to back. First save the next node, then point the current node to the previous node, and then move the node downwards to continue the cycle for the next reversal.

 1     public ListNode reverseList(ListNode head) { 2         if (head == null) { 3             
 return null; 4         } 5         ListNode pre = null; 6         
 ListNode next = null; 7         while (head != null) { 8             
 // 保存下个节点,防止丢失 9             next = head.next;10             
 // 将他的下个节点指向前个节点11             head.next = pre;12 13             
 // head指向pre后，就继续依次反转下个节点14             
 // 让pre，head依次向后移动一个节点，继续下一次的反转15             
 pre = head;16             head = next;17         }18         
 return pre;19     
 }

As soon as I finished the online programming, I recorded it for easy reference in the future.

The above is the detailed content of Commonly used operations on linked lists - detailed explanation of reversal. For more information, please follow other related articles on the PHP Chinese website!