To the chase

Reverse linked list II

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:

Input: head = [1,2,3,4,5], left = 2, right = 4Copy the code

Example 2:

Input: head = [5], left = 1, right = 1 output: [5]Copy the code

1. How do you reverse a linked list? 2

If you figure out how to flip a linked list from scratch, then this problem is easier to solve. Just on this basis, reverse from different positions to different positions, then we can give the following idea:

If you can use a GIF to explain the problem, never type!

Step 1: Create a method to flip the full list

var reverse = function (head, end) { let pre = end let cur = head while(cur ! == end) { const next = cur.next cur.next = pre pre = cur cur = next } return pre }Copy the code

End indicates the position before end, and splice the list with end, so in century operation it looks like this:

The nice thing about this is that you just reverse the end, and you just splice the tail. Finally, the head can be spliced.

Boundary problem:

  1. If there is only one node in the list, return that node directly
  2. There is no header splicing problem if the list to be flipped starts at the first node

Complete 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 reverse = function (head, end) { let pre = end let cur = head while(cur ! == end) { const next = cur.next cur.next = pre pre = cur cur = next } return pre } var reverseBetween = function(head, left, right) { if (head.next === null) { return head } let tempHead = head let tempEnd = head let index = 1 let pre = null let  after = null while(index < right) { if (index < left) { pre = tempHead tempHead = tempHead.next } tempEnd = tempEnd.next index++ } after = tempEnd.next console.log({tempHead, after}) const newList = reverse(tempHead, after) console.log({newList, pre}) pre ? pre.next = newList : head = newList return head };Copy the code