Sword finger Offer 24. Reverse the linked list

The question

Sword finger Offer 24. Reverse the linked list

solution

1. Three-pointer (two-pointer)

The general idea is that for three consecutive nodes A->B->C, three Pointers pre, P and TEP are used to correspond one by one.

Disconnect B -> C and connect B -> A (at this point, the linked list is split in two, but the second linked list where C node is located still points to TEP pointer, so it will not be lost).
Then, the three Pointers all move one node to the right, because TEP is the first node, so it needs to judge whether it is empty or not, it moves forward.
Repeat the first step.
Exit the loop when p is null.
The next of the original head node also points to the second node, which needs to be changed here.

The essence of this method is to repoint the latter node to the former node for inversion. Tep is used to save the second linked list composed of the remaining nodes and add the values of the second linked list to the first one in turn.

2. Recursively

Leetcode’s solution, for details, click # [reverse linked list] : Double pointer, recursive, demonized double pointer

First find the last element by recursionhead.next === null
Each time the function returns, the value of the next node of the current nodenextPointer to current node.
At the same time, let the next pointer of the current node point to NULL, thus achieving local inversion from the end of the list.

Pay attention to

Here, once the last res is found, the RES is not modified, only the res is returned layer by layer

3. Demonized double Pointers

Leetcode’s solution, for details, click # [reverse linked list] : Double pointer, recursive, demonized double pointer

And the idea of a double pointer is similar, the difference is how to record the position of the unreversed list.

code

1. Three-pointer (two-pointer)

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head)return null
    if(! head.next)return head
    let pre = head
    let p = head.next
    let tep = head.next.next
    while(p){
        p.next = pre
        pre = p
        p = tep
        if(tep)tep = tep.next
        
    }
    head.next = null
    return pre
};
Copy the code

2. Recursively

var reverseList = function(head) {
    if(head === null||head.next === null) {return head
    }
    let res = reverseList(head.next)
    head.next.next = head
    head.next = null
    return res
};
Copy the code

3. Demonized double Pointers

var reverseList = function(head) {
    if(head === null) return null
    let p = head
    while(head.next ! = =null) {let tep = head.next.next
        head.next.next = p
        p = head.next
        head.next = tep
    }
    return p
};
Copy the code

Sword finger Offer 24. Reverse the linked list