力扣挑战赛第4天-No.92反转链表2

题目描述

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

示例：

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

注意：

1 <= m <= n <= 链表长度。

解法一

穿针引线：记录待反转区域的前一个节点和后一个节点，反转待反转区域，并调整指针指向。

/**
 * 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}
 */
const reverseBetween = function (head, left, right) {
  const reverseLinkList = function (interHead) { // 反转链表
    let _prev = null;
    let _curr = interHead;
    while (_curr) {
      let _nextTemp = _curr.next;
      _curr.next = _prev;
      _prev = _curr;
      _curr = _nextTemp;
    }
  }

  let dummyNode = new ListNode(-1); // 设置虚拟节点
  dummyNode.next = head;

  /* 获取待反转区域的前一个节点 */
  let prev = dummyNode;
  for (let i = 0; i < left - 1; i++) {
    prev = prev.next;
  }

  /* 获取待反转区域中的最后一个节点 */
  let rightNode = prev;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }

  let leftNode = prev.next; // 获取待反转区域中的第一个节点
  let curr = rightNode.next; //获取待反转区域的后一个节点

  /* 截断链表 */
  prev.next = null;
  rightNode.next = null;

  reverseLinkList(leftNode); // 反转待反转区域

  /* 将反转后的子链表连接回原来的链表中 */
  prev.next = rightNode;
  leftNode.next = curr;

  return dummyNode.next;
};

解法二

穿针引线之原地反转：在遍历待反转区域时，原地调整节点的指针指向，详见：一次遍历-反转链表

/**
 * 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}
 */
const reverseBetween = function (head, left, right) {
  let dummyNode = new ListNode(-1);
  dummyNode.next = head;

  let prev = dummyNode;
  for (let i = 0; i < left - 1; i++) {
    prev = prev.next;
  }

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

  return dummyNode.next;
}

Donate