92. Reverse Linked List II

🟠   🔖  链表  🔗 LeetCode

题目

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

Example 2:

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

Output: [5]

Constraints:

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

Follow up: Could you do it in one pass?

题目大意

给定 2 个链表中结点的位置 m, n，反转这个两个位置区间内的所有结点。

解题思路

• 由于有可能整个链表都被反转，所以构造一个新的头结点指向当前的头；
• 找到第一个需要反转的结点的前一个结点 p，从这个结点开始，依次把后面的结点用“头插”法，插入到 p 结点的前面；
• 循环次数用 n-m 来控制。

代码

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
  if (!head || left === right) return head;

  let res = new ListNode(0, head);
  let prev = res;

  // 移动prev指针，直至指向left - 1
  for (let i = 0; i < left - 1; i++) {
    prev = prev.next;
  }

  let cur = prev.next;

  // 不断地将 cur.next 插入到 prev.next
  for (let i = 0; i < right - left; i++) {
    let temp = cur.next;
    cur.next = temp.next;
    temp.next = prev.next;
    prev.next = temp;
  }

  return res.next;
};

相关题目

相关题目

• 206. 反转链表

- [206. 反转链表](./0206.md)