• Topic describes
    • Give you the head pointer to a singly linked listheadAnd two integersleft 和 right, includingleft <= right. Please reverse from positionLeft to the list node at position right, returns the reversed linked list.

Example 1:

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

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 with the head of the child list, that is, preleft. next = rightNode

  4. Back to the head

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

Welcome to the triad discussion