Const
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) } }
要反转链表的一部分,做法基本操作跟反转整条链表是一样的。同样需要设计三个指针pre、cur、nxt。其中pre指向当前节点的前一个节点,cur指向当前节点,nxt指向当前节点的下一个节点。利用头插法完成反转。同样地,pre、cur、nxt具有另一层意思:
特殊情况,当left为1的时候,反转部分的前一个节点是无法找到p0的,为了统一逻辑,我们引入一个虚拟头节点dummy,让dummy的next指向head。这样子我们就可以认为当left为1的时候,p0就是dummy。
现在我们需要完成k个一组反转链表。那么我们其实就是在循环反转链表的一部分,做法基本跟上面反转一部分链表一样,只不过反转之前我们先判断下剩余节点个数,如果大于等于K,我们可以反转,否则我们退出循环。
需要注意的是,我们在多次反转链表的一部分的时候,p0不再是像上面那样固定不变的,而是需要每次反转前重新计算p0。将p0更新成下一段要反转的节点的上一个节点。而我们知道,在一部分反转结束之后,pre就是反转部分的头部,而cur在pre后边,如果反转部分后,其实pre代表的这段部分的尾部会接上cur,这个尾部实际上就是没完成拼接工作之前,p0的next节点,因此我们可以在修改前将这个节点保存起来。
/**
* 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 reverseKGroup(head: ListNode | null, k: number): ListNode | null {
let n = 0; // 先算出整个链表的长度
for (let cur = head; cur !== null; cur = cur.next) {
n++;
}
const dummy = new ListNode(-1, head);
let p0 = dummy;
let pre = null;
let cur = p0.next!;
// K个一组,循环反转
while (n >= k) {
n -= k;
// 反转K个
for (let i = 0; i < k; i++) {
const nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt!;
}
const nxtP0 = p0.next!;
nxtP0.next = cur;
p0.next = pre;
p0 = nxtP0;
}
return dummy.next;
};
// 递归解法
function reverseKGroup1(head: ListNode | null, k: number): ListNode | null {
// 判断是否小于k,如果小于k,一定会在循环中return head
let p = head;
for (let i = 0; i < k; i++) {
if (p === null) {
return head;
}
p = p.next;
}
// 反转k个链表
let pre: ListNode | null = null;
let cur: ListNode | null = head;
let nxt: ListNode | null = null;
// 1->2->3->4->null
for (let i = 0; i < k; i++) {
nxt = cur!.next;
cur!.next = pre;
pre = cur;
cur = nxt;
}
// k个一组反转后,原本的头就变成了这组的尾,继续反转下一组
head!.next = reverseKGroup(cur, k);
return pre;
};
25.K 个一组翻转链表
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯地改变节点内部的值,而是需要实际进行节点交换。
示例 1:
输入:
head = [1,2,3,4,5], k = 2
输出:
[2,1,4,3,5]
示例 2:
head = [1,2,3,4,5], k = 3
输出:
[3,2,1,4,5]
提示:
n
1 <= k <= n <= 5000
0 <= Node.val <= 1000