Subject to introduce

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Example 1

Enter: head = [1.2.3.4.5], left = 2, right = 4Output:1.4.3.2.5]
Copy the code

Example 2

Enter: head = [5], left = 1, right = 1Output:5]
Copy the code

Tip:

• The number of nodes in the list isn
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Leetcode -92 Reverse linked list II B station video

Their thinking

Thinking a

The inverted part of the linked list is first cut off from the original list, and then inserted into the original list after the inversion

1. Create a virtual head node. The next node of the virtual head node points to head node 2. 3. Pre and CUR iterate until Pre is at the top of the list to be reversed and CUR is at the top of the list to be reversed. 4. Cur iterate until pre is at the end of the list to be reversed. Create a next pointer to the next node of cur and point the next node to NULL 5. Reverse the list with pre-.next as the head node, as shown in [luffy]_ reverse the list 6. Point the next node of the pre node to the head of the reversed list, and point the next node of the tail of the reversed list to next

The problem solving code

// Reverse the linked list
var reverseList = function(head, next) {
    let pre = head, cur = head.next
    while (head.next) {
        head.next = cur.next
        cur.next = pre
        pre = cur
        cur = head.next
    }
    head.next = next
    return pre
}
Copy the code

var reverseBetween = function(head, left, right) {
    const newHead = new ListNode(-1, head)
    let pre = newHead, cur = head, next
    let n = right - left + 1
    while(--left) {
        // Reverse the previous node of the list
        pre = pre.next
        // Invert the node at the beginning of the list
        cur = cur.next
    }
    while(--n) {
        // Reverse the end of the list
        cur = cur.next
    }
    // Invert the next node in the list
    next = cur.next
    cur.next = null
    const reverseHead = reverseList(pre.next, next)
    pre.next = reverseHead
    return newHead.next
};
Copy the code

Idea 2 (Head insertion method)

Insert each traversed node of the list to be reversed (except the head node) between the previous node of the reversed list and the current node of the reversed list

1. Create a virtual head node. The next node of the virtual head node points to head node 2. Create a pre pointer to the virtual head node and a cur pointer to the virtual head node 3. Pre and cur iterate until Pre is at the previous head node and cur is at the head node 4 of the list to be reversed. Create q pointer to the next node of cur (cur) 5. Point q’s next node to pre’s next node 7. Point Pre’s next node to Q 8. Repeat the process 4-7 until the list to be reversed ends

The problem solving code

var reverseBetween = function(head, left, right) {
    const newNode = new ListNode(-1, head)
    let pre = newNode, cur = head
    let n = right - left + 1
    while (--left) {
        pre = pre.next
        cur = cur.next
    }
    while (--n) {
        const q = cur.next
        cur.next = q.next
        q.next = pre.next
        pre.next = q
    }
    return newNode.next
};
Copy the code

Circular linked list II circular linked list II circular flying _ happy number [flying]_ reverse linked list