LeetCode 92. 反转链表 II

作者:Choi Yang

更新于:7 个月前

字数统计:517 字

阅读时长:2 分钟

题目描述

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

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

借助递归

/**
 * 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) {
  let reverse = (pre, cur) => {
    if (!cur) return pre;
    let tmp = cur.next;
    cur.next = pre;
    return reverse(cur, tmp);
  };
  let dummyHead = new ListNode();
  dummyHead.next = head;
  let p = dummyHead;
  let k = m - 1;
  // 先找到需要反转链表部分的前驱节点
  while (k--) {
    p = p.next;
  }
  // 保存前驱节点
  let front = p;
  // 找到需要反转链表部分的头节点
  let frontNode = front.next;
  k = n - m + 1;
  // 再找到需要反转链表部分的尾节点
  while (k--) {
    p = p.next;
  }
  // 找到需要反转链表部分的尾节点
  let endNode = p;
  // 保存后继节点
  let end = endNode.next;
  // 将后继值为空，开始反转链表
  endNode.next = null;
  front.next = reverse(null, frontNode);
  // 原本的反转链表部分的头节点现在变成了尾节点，指向原本的后继节点
  frontNode.next = end;
  return dummyHead.next;
};

迭代解法

/**
 * 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) {
  let dummyHead = new ListNode();
  dummyHead.next = head;
  let p = dummyHead;
  let k = m - 1;
  // 先找到需要反转链表部分的前驱节点
  while (k--) {
    p = p.next;
  }
  // 保存前驱节点
  let front = p;
  let pre = (frontNode = front.next);
  let cur = pre.next;
  k = n - m;
  // 长度为3的链表需要反转2次，那么长度为n的链表需要反转n-1次
  while (k--) {
    let tmp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = tmp;
  }
  // 将原本前驱节点的next指向当前反转后的链表
  front.next = pre;
  // 原本反转链表的头节点现在变成了尾结点，指向后继节点
  frontNode.next = cur;
  return dummyHead.next;
};

学如逆水行舟，不进则退

Contributors

Choi Yang