Skip to main content

反转链表-ii

Tips

题目类型: LinkedList

相关题目:

题目​

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

示例

输入: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, left = 2, right = 4

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

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

题解​

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

  let prev = dummy,
    curr = dummy.next

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

  for (let i = 0; i < right - left; i++) {
    const removed = curr.next
    curr.next = curr.next.next
    removed.next = prev.next
    prev.next = removed
  }

  return dummy.next
}