92. Reverse linked list II

Answer:

  1. Refer to theThe official answer keyIn theMethod two: Iterative link inversionYou can understand the pictures.
  2. If you’re not familiar with reverse lists, try 206. reverse lists first.
  3. Use the prev and curr Pointers for list inversion by moving the two Pointers to m-1 and M first.
  4. In reverse, the list is split into three segments, with the first and third segments unchanged and the middle segment reversed.
  5. After the list is reversed, m-1 node is the end of the first linked list. The m node goes from the head of segment 2 to the end of the list of segments 2. The pointer to curr moves to the head of the third list. If the third list does not exist, curr isnull.
  6. Finally, join the three linked lists. Note that if m is 1, that is, if the first list does not exist, the head of the list has actually become the head of the second list, so you need to set the head again.
/ * * *@param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}* /
var reverseBetween = function(head, m, n) {
  let prev = null // A leading pointer for inversion
  let curr = head // The current pointer for inversion 98j9

  // Move both prev and head m-1 times, prev at m-1 and head at m
  while (m > 1) {
    prev = curr
    curr = curr.next
    // Reduce m by 1 for each loop to control the number of moves
    m--
    // When moving the pointer, we need to reduce the number of n. After completing the move, we need to reverse the list n times
    n--
  }

  let prevListTail = prev // prev is a pointer to the end of the first half of the list
  let reversedListTail = curr // curr is the tail pointer to the reversed part of the linked list

  // Invert the list n times
  while (n > 0) {
    // General method of reversing linked list nodes
    let next = curr.next
    curr.next = prev
    prev = curr
    curr = next
    // Reduce n by 1 for each loop to control the number of moves
    n--
  }

  // If the prevListTail is not empty, the middle section of the list has been reversed, and the first half needs to be joined to the reversed pointer
  if (prevListTail) {
    // After the list is reversed, the position of the prev is the head pointer of the reversed part
    prevListTail.next = prev
  } else {
    // If the list is not empty, it means that the list is reversed from the beginning. The reversed prev is the head of the new list, so we need to reset the head pointer of the list
    head = prev
  }

  // After the list is reversed, the original head of the reversed part becomes the tail, and the curr has been added and removed from the list to become the head pointer of the last list
  // So we need to join the tail pointer of the inverted segment with the head pointer of the last segment to form a new list
  reversedListTail.next = curr

  return head
};
Copy the code