Topic describes

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 output: [1,4,3,2,5]

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?

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Here is an example of the reverse of the linked list in yellow:

After reversing left to right, splice together. We also need to record the first node of left and the last node of right. As shown in the figure:

Algorithm steps

  1. First reverse the region to be reversed
  2. Put pre’s next pointer to the inverted head of the list and suCC’s next pointer to the inverted tail.

code

* Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} left * @param {number} right * @return {ListNode} */ var reverseBetween = function(head, left, right) { if(! head) return null; Let ret = new ListNode(-1,head),pre = ret, CNT = right-left + 1; let ret = new ListNode(-1,head),pre = ret, CNT = right + 1; While (--left){pre = pre. Next; Next = reverse(pre.next, CNT); return ret.next; }; var reverse = function(head,n){ let pre = null,cur =head; // After the head node of the region to be reversed is reversed for n times (n is the length of the region to be reversed), While (n--){[cur.next,pre,cur]=[pre,cur. Next]} return pre; }Copy the code