“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

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.

LeetCode leetcode-cn.com/problems/re…

Their thinking

  1. Find the left and right nodes and record that the first node of left is prevLeft and the next node of right is rightNext
    • Go right from headleft - 1The step is left
    • Go from left to rightright - leftStep is right
  2. After finding left and right, flip the next node of left to the previous node of right
    • Curr points to left and flips from left
    • Prev points to rightNext so that when the child list is flipped, the first node is connected to the second half
    • Once curr and prev are defined, sublists can be flipped
  3. After flipping the child list, join the first half of the child list with the head, i.epreLeft.next = rightNode
  4. Back to the head

For example

[1, 2, 3, 4, 5, 6, 7], left = 3, right = 5

Step 1: Find the third and fifth nodes

Step 2: Flip the left to right child list, and point the tail of the child list to the next node of right, and point the first node of the left to the first node of the child list

Code implementation

var reverseBetween = function(head, left, right) { if (! head || ! head.next || left === right) return head let curr = head let prev = next = null let leftNode = prevLeft = rightNode = RightNext = null let step = left - 1 While (step--) {prevLeft = curr curr = curr.next} leftNode = curr prevLeft. Next = null Step = right-left while (step--) {curr = curr.next} rightNode = curr rightNext = curr.next Rightnode. next = null // Invert the child list between left and right curr = leftNode prev = rightNext while (curr) {next = curr.next PrevLeft. Next = rightNode return head}Copy the code

If there are mistakes welcome to point out, welcome to discuss together!