数据结构与算法之链表: LeetCode 92. 反转链表 II (Ts版)

反转链表 II

• https://leetcode.cn/problems/reverse-linked-list-ii/description/

描述

• 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right
• 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表

示例 1

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2

输入：head = [5], left = 1, right = 1
输出：[5]

提示

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n
• 进阶： 你可以使用一趟扫描完成反转吗？

Typescript 版算法实现

1 ) 方案1: 穿针引线

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/const reverseLinkedList = (head: ListNode | null) => {let pre = null;let cur = head;while (cur) {const next = cur.next;cur.next = pre;pre = cur;cur = next;}
}function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论const dummyNode = new ListNode(-1);dummyNode.next = head;let pre = dummyNode;// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点// 建议写在 for 循环里，语义清晰for (let i = 0; i < left - 1; i++) {pre = pre.next;}// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点let rightNode = pre;for (let i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}// 第 3 步：切断出一个子链表（截取链表）let leftNode = pre.next;let curr = rightNode.next;// 注意：切断链接pre.next = null;rightNode.next = null;// 第 4 步：同第 206 题，反转链表的子区间reverseLinkedList(leftNode);// 第 5 步：接回到原来的链表中pre.next = rightNode;leftNode.next = curr;return dummyNode.next;
};

2 ) 方案2: 一次遍历「穿针引线」反转链表（头插法）

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {// 设置 dummyNode 是这一类问题的一般做法const dummy_node = new ListNode(-1);dummy_node.next = head;let pre = dummy_node;for (let i = 0; i < left - 1; ++i) {pre = pre.next;}let cur = pre.next;for (let i = 0; i < right - left; ++i) {const next = cur.next;cur.next = next.next;next.next = pre.next;pre.next = next;}return dummy_node.next;
};

3 ）方案3：局部反转法

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {const dummy = {next: head}let tmp = dummyfor (let i = 0; i < left - 1; i++) {tmp = tmp.next}let prev = tmp.nextlet cur = prev.nextfor (let j = 0; j < right - left; j++) {let next = cur.nextcur.next = prevprev = curcur = next // cur = cur.next}tmp.next.next = curtmp.next = prevreturn dummy.next
};