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

反转链表 II

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

形貌

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

示例 1

   

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

复制代码

示例 2

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

复制代码

提示

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

Typescript 版算法实现


1 ) 方案1: 穿针引线

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     val: number
5. *     next: ListNode | null
6. *     constructor(val?: number, next?: ListNode | null) {
7. *         this.val = (val===undefined ? 0 : val)
8. *         this.next = (next===undefined ? null : next)
9. *     }
10. * }
11. */
13. const reverseLinkedList = (head: ListNode | null) => {
14.     let pre = null;
15.     let cur = head;
17.     while (cur) {
18.         const next = cur.next;
19.         cur.next = pre;
20.         pre = cur;
21.         cur = next;
22.     }
23. }
25. function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
26.     // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
27.     const dummyNode = new ListNode(-1);
28.     dummyNode.next = head;
30.     let pre = dummyNode;
31.     // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
32.     // 建议写在 for 循环里，语义清晰
33.     for (let i = 0; i < left - 1; i++) {
34.         pre = pre.next;
35.     }
37.     // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
38.     let rightNode = pre;
39.     for (let i = 0; i < right - left + 1; i++) {
40.         rightNode = rightNode.next;
41.     }
43.     // 第 3 步：切断出一个子链表（截取链表）
44.     let leftNode = pre.next;
45.     let curr = rightNode.next;
47.     // 注意：切断链接
48.     pre.next = null;
49.     rightNode.next = null;
51.     // 第 4 步：同第 206 题，反转链表的子区间
52.     reverseLinkedList(leftNode);
54.     // 第 5 步：接回到原来的链表中
55.     pre.next = rightNode;
56.     leftNode.next = curr;
57.     return dummyNode.next;
58. };

复制代码

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

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     val: number
5. *     next: ListNode | null
6. *     constructor(val?: number, next?: ListNode | null) {
7. *         this.val = (val===undefined ? 0 : val)
8. *         this.next = (next===undefined ? null : next)
9. *     }
10. * }
11. */
13. function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
14.     // 设置 dummyNode 是这一类问题的一般做法
15.     const dummy_node = new ListNode(-1);
16.     dummy_node.next = head;
17.     let pre = dummy_node;
18.     for (let i = 0; i < left - 1; ++i) {
19.         pre = pre.next;
20.     }
22.     let cur = pre.next;
23.     for (let i = 0; i < right - left; ++i) {
24.         const next = cur.next;
25.         cur.next = next.next;
26.         next.next = pre.next;
27.         pre.next = next;
28.     }
29.     return dummy_node.next;
30. };

复制代码

3 ）方案3：局部反转法

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     val: number
5. *     next: ListNode | null
6. *     constructor(val?: number, next?: ListNode | null) {
7. *         this.val = (val===undefined ? 0 : val)
8. *         this.next = (next===undefined ? null : next)
9. *     }
10. * }
11. */
13. function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
14.     const dummy = {
15.         next: head
16.     }
17.     let tmp = dummy
18.     for (let i = 0; i < left - 1; i++) {
19.         tmp = tmp.next
20.     }
22.     let prev = tmp.next
23.     let cur = prev.next
25.     for (let j = 0; j < right - left; j++) {
26.         let next = cur.next
27.         cur.next = prev
28.         prev = cur
29.         cur = next // cur = cur.next
30.     }
32.     tmp.next.next = cur
33.     tmp.next = prev
35.     return dummy.next
36. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。