ChoDocs

外观

LeetCode 92. 反转链表 II ​

作者:Choi Yang
更新于:17 小时前
字数统计:515 字
阅读时长:2 分钟

题目描述 ​

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

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

示例:

javascript
输入: 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

借助递归

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

迭代解法

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

Contributors ​

Choi Yang
文章作者：Choi Yang
文章链接：
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ChoDocs！