Reverse a linked list
Take a one-way list, reverse it, and return the reversed list. Example: 1->2->3->4->5 converts to 5->4->3->2->1
Idea 1: Define multiple Pointers for interchangeability
- Let’s define three Pointers: pre (head of the unreversed list) cur (head of the unreversed list) Next (next bit of the unreversed list)
- The first step is to make pre point to empty, CUR point to the current head node, and Next point to the next node of the current cur.
- The second step is to have cur point to pre, then move pre to cur, cur to Next, and Next to the next node
- Repeat the second step until the list reaches the end, and then return pre to reverse the list.
Idea 1: JS code implementation
var reverseList = function(head) {
if(! head)return null;
let pre = null; // Reverse the header of the list
let cur = head; // No reverse header
let next = head.next; // Next node
while (cur) {
cur.next = pre; // The next bit of the current node points to pre
pre = cur; // Pre moves to the current list head node
cur = next; // Move the current head node one bit back
next && (next = next.next) // If the next bit is not empty, the list still has a value, and the next bit moves one more bit, thus completing a node inversion and continuing the loop until the list ends.
}
return pre; // return the reverse list header
};
Copy the code
Idea 2: Recursion
When switching, the current node is assigned to the next node after the switching node.
Idea 2: code implementation
var reverseList = function(head) {
if(! head)return head; // If the list is empty, return the current list
if(! head.next)return head; // If the list has only one digit, the current list is also returned
let next = head.next; // Next node
let p = reverseList(head.next); // Get the inverted list head node
head.next = next.next; // Reverse the current node
next.next = head; // Connect the next node back to the current head node (1, 2, 3), the current node is 2, then connect 3->2, finally connect 1 to 2, then connect 3->2->1
return p;
};
Copy the code