Topic describes

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.

Analysis of the

Input: head Output: returns the flipped head

Their thinking

If we have a list going from 1 to 5, left at 2, right at 4, what we need to flip is between 2 and 4

Here, we also need to record the precursor node pre and the successor node SUCC in this interval. This is done so that, after the flip, next of the precursor node and next of the last node of the flipped part point to the correct node.

One thing to notice here is that left, right, is just an index, it doesn’t give us the actual node. Therefore, we need to find these two nodes by ourselves, and I will name them leftNode, rightNode, pre, succ, so as to do the corresponding operations.

That’s essentially looking for pre, rightNode, leftNode, succ which is their next point.

To make less judgment, we introduce a dummyHead with its next pointing to head. Our search process starts with dummyHead.

OK, so let’s go to pre, now the key is, how many steps from dummyHead can I get to the correct node?

I recommend using a for loop, because the number of steps you need to take can be used as a condition for termination of the for loop. Let’s take an example 🌰 :

Let’s say I take two steps,

for (let i = 0; i < 2; i++) {
    console.log(`I have moved '${i + 1}' steps`)}Copy the code

Obviously the for loop is executed twice, so if the variable moves one step in the list each time, it moves two steps. This process can be justified.

We use this principle to observe the correspondence between left and Pre.

The difference between pre and left is 1. If left is 2, then the process of finding pre looks like this:

DummyHead ➡ ️ 1 (the head)

It’s actually a step, left-1

So find the code for Pre:

for (let i = 0; i < left - 1; i++) {
    pre = pre.next
}
Copy the code

So for rightNode, let’s do the same thing, look at right and Pre,

Right at 4, prev at 1, right and left 2,

So for the pre you already found, you need to go right-left + 1.

The corresponding code is:

rightNode = pre
for (let i = 0; i < right -left + 1; i++) {
    rightNode = rightNode.next
}
Copy the code

Once we find them, we also find leftNode, suCC

For the flipping process, we also have a fixed template to solve:

function reverseList(head) {
    // Switch the position between the previous node and the current node
    let pre = null,
        cur = head
        
    // As long as there are nodes to swap, keep going
    while (cur) {
        // Because we want the next of the current node to point to the previous node, we use a variable to store the current next ~
        const tmp = cur.next
        cur.next = pre
        pre = tmp
        
        cur = cur.next
    }
}
Copy the code

And then finally connect the inverted list to the rest of the outside, to pre and SUCC.

Let’s just look at the overall code

code

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}* /
var reverseBetween = function (head, left, right) {
  let leftNode, rightNode, pre, succ;
  const dummyHead = new ListNode(null, head);
  pre = dummyHead;

  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }

  rightNode = pre;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }

  succ = rightNode.next;
  leftNode = pre.next;
  pre.next = null;
  rightNode.next = null;

  reverseList(leftNode);
  function reverseList(head) {
    let prev = null;
    let cur = head;

    while (cur) {
      const tmp = cur.next;

      cur.next = prev;
      prev = cur;
      cur = tmp;
    }
  }

  pre.next = rightNode;
  leftNode.next = succ;

  return dummyHead.next;
};
Copy the code

The complexity of the

Time: O(N), traversing the whole list at most twice. If the part to be reversed is close to the whole length space: O(1), only a few Pointers need to be saved