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

Reverse linked lists II

The title

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 = 4

Example 2:

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

 

Tip:

The number of nodes in the linked list is N 1 <= n <= 500-500 <= node. val <= 500 1 <= left <= right <= n

Advancements: Can you use one scan to complete the inversion?

Answer key

Ask questions

  • How to partially reverse and in the process, how to keep the next node of the linked list node from being lost?

Analysis of the iteration

  • Looking at the reversed list from Example 1, if you want to reverse the list from left nodes to right nodes, that is, the parts 2-4 are reversed.

  • First define a temp virtual node and point temp.next to the head node

  • The pre to temp

  • Cur points to the next node of the node that cur points to, that is, to the head node

  • willcur,preThe needle moves backwards at the same time untilleftA node

  • defineconwithtail.conPoint to thepreThe node that points to,tailPoint to thecurThe node pointed to.
  • conThe node pointed to will be the head node of the part we want to reverse.
  • tailIs the tail node of the reverse part.

  • This goes into the reverse linked list link, first definednextPointer tocurThe next node of the node pointed to.

  • thencurThe node toperNode,prePointer moved tocurPointer position, willcurMove to thenextPointer position, untilperPointer torightA node.

  • Repeat the preceding steps whenperPointer toright“Indicates that the entire list of parts that need to be reversed is completed.

  • willconThe node to which the pointer points points points nowpreThe node to which the pointer points.
  • willtailThe node to which the pointer points points points nowcurThe node to which the pointer points.

  • Tidy it up

Code implementation

/** * @param {ListNode} head * @param {number} left * @param {number} right * @return {ListNode} */ var reverseBetween =  function(head, left, right) { if(! head) return null let temp = new ListNode(-1,head) pre = temp cnt = right-left+1 while(--left){ pre = pre.next } pre.next = reverse(pre.next,cnt) return ret.next }; var reverse = function(head,n){ let pre = null let cur = head while(n--){ [cur.next,pre,cur]=[pre,cur,cur.next]; } head.next = cur return pre }Copy the code