(Summarized from labuladong’s algorithm cheat sheet, I recommend this book to you)

1. Reverse the entire single linked list (leetcode#206)

// The loop method
var reverseList = function(head) {
    let pre = null, cur = head
    while(cur) {
        let tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }
    return pre
};

// The recursive method
var reverseList = function(head) {
    if(! head || ! head.next)return head
    let newHead = reverseList(head.next)
    head.next.next = head
    head.next = null
    return newHead
};
Copy the code

A few points to note about the recursive solution:

A. For all recursion problems, firmly believe in the definition of a recursive function, including parameters and return values. ReverseList passes in a list head node, reverses the list and returns its new head node, and does not fall into the recursive trap.

B. In essence, it is the sequential traversal of the linked list. Stack one by one, after encountering base case, assemble the reversed linked list from the last one, and then stack one by one;

C. Recursive solutions to this problem also provide us with solutions to complex problems

2. Reverse the first N nodes of the list

example case:

n = 3

1 – > 2 – > 3 – > 4 – > 5 = 5 < < < – 4-1-2 < 3

let successor
var reverseN = function (head,n) {
    if (n === 1){
        successor = head.next
        return head
    }
    const newHead = reverseN(head.next,n-1)
    head.next.next = head
    head.next = successor
    return newHead
}
Copy the code

The idea of recursion is the same, except that a global variable is required to record the next of the last inverted node as the next of the head node before the inverted node.

3. Reverse part of the linked list (leetcode#92)

var reverseBetween = function(head, left, right) {
    if(left === 1) {
        return reverseN(head,right)
    }
    head.next = reverseBetween(head.next,left-1,right-1)
    return head
    
};

let successor
var reverseN = function (head,n) {
    if (n === 1){
        successor = head.next
        return head
    }
    const newHead = reverseN(head.next,n-1)
    head.next.next = head
    head.next = successor
    return newHead
}
Copy the code

The idea of recursion is more obvious here, inverting left to right of head list means inverting head. Next left-1 to right-1 of the list, base case is ab initio inversion, that is, inverting the first n nodes of the list in question 2.

4. A group of K reverse linked lists

var reverseKGroup = function (head, k) {
    if(! head)return null
    let headNxt = head
    // If the length of the list is greater than or equal to k, it also finds the k+1 node as the entry of recursion
    for(let i = 0; i < k; i++){
        if(! headNxt)return head
        headNxt = headNxt.next
    }
    let newHead = reverseK(head, headNxt)
    // head is now the last node in the first half of the current list
    // Head < -1, 3->4->5
    head.next = reverseKGroup(headNxt,k)
    return newHead
}

// This is similar to the loop-reversed list, except that the terminating condition is changed to Node
var reverseK = function(head, node) {
    let cur = head, pre = null
    while(cur ! == node){let tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }
    return pre
}
Copy the code