数据结构与算法之链表: LeetCode 92. 反转链表 II (Ts版)
反转链表 II[*]https://leetcode.cn/problems/reverse-linked-list-ii/description/
形貌
[*]给你单链表的头指针 head 和两个整数 left 和 right ，此中 left <= right
[*]请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
示例 1
https://i-blog.csdnimg.cn/direct/96a00e7f368b470ca9b96f77869c25c8.png输入：head = , left = 2, right = 4
输出：
示例 2
输入：head = , left = 1, right = 1
输出：
提示
[*]链表中节点数目为 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 = dummy
for (let i = 0; i < left - 1; i++) {
tmp = tmp.next
}
let prev = tmp.next
let cur = prev.next
for (let j = 0; j < right - left; j++) {
let next = cur.next
cur.next = prev
prev = cur
cur = next // cur = cur.next
}
tmp.next.next = cur
tmp.next = prev
return dummy.next
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]