92.反转链表 II

92.反转链表 II

Category	Difficulty	Likes	Dislikes
algorithms	Medium (55.12%)	1179	-

Tags
Companies
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

---

Discussion | Solution

思路

首先，我们定义一个新的节点 head，将其值设为 0，并将其 next 指向原来的头节点 head，这么做是为了防止 head 节点在反转时被移除。
然后，定义三个指针 cur、prev、temp 和两个辅助节点 front、tail。其中，cur 指向当前遍历的节点，prev 指向 cur 的前一个节点，temp 用于存储下一个节点的地址，front 用于记录第 left-1 个节点，tail 用于记录第 right+1 个节点。
接下来，我们需要将 cur 指向第 left 个节点，同时记录下 cur 的前一个节点，并将前一个节点的 next 指向 null。这么做的原因是，我们需要在反转链表时避免将链表的其他节点也反转。
接着，我们对第 left 到第 right 个节点进行反转，具体做法是：每次将 cur 的 next 指向 prev，然后将 prev 指向 cur，cur 指向 temp，直到 cur 遍历到第 right+1 个节点。此时，prev 指向的就是第 right 个节点，cur 指向的就是第 right+1 个节点。
最后，我们将前面的链表和反转后的链表拼接起来。具体做法是：将 front 的 next 指向 prev，将 tail 的 next 指向 cur，然后返回 head 的 next 节点，也就是反转后的链表的头节点。

解答

/*
 * @lc app=leetcode.cn id=92 lang=javascript
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * 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) {
  head = new ListNode(0, head);
  let count = 1,
    cur = head,
    prev = null,
    temp = null,
    front = null,
    tail = null;
  while (count <= left) {
    prev = cur;
    cur = cur.next;
    count++;
  }
  prev.next = null;
  front = prev;
  prev = null;
  while (cur && count <= right + 1) {
    if (!tail) tail = cur;
    temp = cur.next;
    cur.next = prev;
    prev = cur;
    cur = temp;
    count++;
  }
  front.next = prev;
  tail.next = cur;
  return head.next;
};

// @lc code=end