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

[B] [C] [D]

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 = 4Copy the code

Example 2:

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

Tip:

  • The number of nodes in the list isn
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

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

The problem is to find the combination of the specified node and the reverse list

The main idea is: first find the interval to be reversed, reverse the interval to be reversed, and then connect back to the original linked list

The detailed solution is as follows:

  1. If left===right, you do not need to reverse the list
  2. Create a virtual head nodevhead.vhead.next = head, the virtual head can facilitate our subsequent operations (for example: if the interval to be reversed contains the head node, the return value will be judged as special, as long as the virtual head is returnedvhead.next)
  3. Define three Pointerspre = vhead 、 start = head 、 end = head
  4. According to theleft 、 rightThe value ofpre 、 start 、 endIs the previous node of the interval to be reversed, and the beginning position and end position of the interval to be reversed
  5. throughend.nextGets the next node of the interval to be reversednextHead
  6. writereverseThe function reverses the interval to be reversed and returns the first and last nodes of the reversed listReverse linked List)
  7. Through the previous recordpreThe pointer joins the inverted head node of the linked list throughnextHeadJoin returns the last node of the list
  8. The last returnvhead.nextCan be

The complete process is as follows:

The code is as follows:

Function reverse(start,end){let pre = start, next = start.next; // Invert the next pointer from back to front while(next! ==end){ const next_next = next.next; next.next = pre; pre = next; next = next_next; } next.next = pre; return [end,start] } var reverseBetween = function(head, left, If (left ===right) return head; if(left ===right) return head; Const vhead = new ListNode(0); vhead.next = head; // let pre = vhead, // start = end = head; While (right>1){left--,right--; if(left>0){ pre = pre.next; start = start.next; } end = end.next; } // Const nextHead = end.next; [start,end] = reverse(start,end); // Link the reversed list interval to the original list. Next = start; end.next = nextHead; return vhead.next; };Copy the code

This completes leetcode-92-reverse linked list II

If you have any questions or suggestions, please leave a comment!