Skip to main content

反转链表-ii

Tips

题目类型: LinkedList

相关题目:

题目​

反转从位置 m 到 n 的链表. 请使用一趟扫描完成反转.

示例

输入: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4

输出: 1 -> 4 -> 3 -> 2 -> 5 -> NULL

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

题解​

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function (head, m, n) {
  const dummyHead = new ListNode(0)
  dummyHead.next = head

  let g = dummyHead,
    p = dummyHead.next

  // 先找到需要反转的起点
  for (let i = 0; i < m - 1; i++) {
    g = g.next
    p = p.next
  }

  for (let i = 0; i < n - m; i++) {
    const removed = p.next
    p.next = p.next.next
    removed.next = g.next
    g.next = removed
  }

  return dummyHead.next
}