Inverts the linked list from position m to n. Use a scan to complete the inversion.

Description: 1 ≤ M ≤ N ≤ The length of the linked list.

Example:

Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL, m = 2, n = 4 output: 1 - > > 4-3 - > 2 - > 5 - > NULLCopy the code

Their thinking

  • The prev pointer is initialized to NULL, and the cur pointer to the head of the linked list
  • Advance the cur pointer step by step, followed by the prev pointer
  • Until the cur reaches the MTH node from the head of the list, which is where we start to reverse the list
  • Two additional Pointers are introduced, called tail and con. The tail pointer points to the MTH node from the head of the list. This node is the tail of the reversed list. The con pointer points to the previous node of the MTH node, which is the head of the new list
  • Tail and con Pointers are initialized at the beginning of the algorithm and called at the end of the algorithm to perform list inversion. As explained above, after reaching the MTH node, the link is iteratively reversed before the two Pointers are used. Iterate until you finish linking to the NTH node. At this point, the prev pointer points to the NTH node.
  • We use the con pointer to join the prev pointer because the node to which the prev pointer currently points (the NTH node) replaces the MTH node. Similarly, we use the tail pointer to join the node after the prev pointer (NTH +1).

Code implementation

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */
var reverseBetween = function(head, m, n) {
    let prev = null
    let cur = head
    while(m-- > 1){
        n--
        prev = cur
        cur = cur.next
    }
    let con = prev
    let tail = cur 
    while(n-- > 0){
        [cur.next,prev,cur] = [prev,cur,cur.next]
    }
    if(con){
        con.next = prev
    }else{
        head = prev
    }
    tail.next = cur 
    return head
};
Copy the code

performance

Time complexity:

Space complexity: