AlgoViz Lab交互式算法学习Algorithms first
K 个一组翻转链表 · 交互式算法学习
每 k 个节点为一组翻转链表。
#25 · 链表
K 个一组翻转链表
Reverse Nodes in k-Group
head = [1,2,3,4,5], k = 2链表3 个关键状态
步骤 1从 pre 向后找到第 k 个节点。
end=21next
→2next
→3next
→4next
→5next
推荐
定位组尾并原地翻转
时间
O(n)空间 O(1)先确认本组有 k 个节点，再用标准链表反转连接。
1function reverseKGroup(head, k) {2 const d = {3 next: head4 };5 let pre = d;6 while (true) {7 let end = pre;8 for (let i = 0; i < k && end; i++) end = end.next;9 if (!end) break;10 const next = end.next;11 let prev = next,12 cur = pre.next;13 while (cur !== next) {14 const t = cur.next;15 cur.next = prev;16 prev = cur;17 cur = t;18 }19 const start = pre.next;20 pre.next = end;21 pre = start;22 }23 return d.next;24}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for singly-linked list.3 * public class ListNode {4 * int val;5 * ListNode next;6 * ListNode() {}7 * ListNode(int val) { this.val = val; }8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12 public ListNode reverseKGroup(ListNode head, int k) {13 ListNode dummy = new ListNode(0, head);14 dummy.next = head;15 ListNode pre = dummy;16 while (pre != null) {17 ListNode cur = pre;18 for (int i = 0; i < k; i++) {19 cur = cur.next;20 if (cur == null) {21 return dummy.next;22 }23 }24 ListNode node = pre.next;25 ListNode nxt = cur.next;26 cur.next = null;27 pre.next = reverse(node);28 node.next = nxt;29 pre = node;30 }31 return dummy.next;32 }33 34 private ListNode reverse(ListNode head) {35 ListNode dummy = new ListNode();36 ListNode cur = head;37 while (cur != null) {38 ListNode nxt = cur.next;39 cur.next = dummy.next;40 dummy.next = cur;41 cur = nxt;42 }43 return dummy.next;44 }45}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
K 个一组翻转链表 · 解法对比
每 k 个节点为一组翻转链表。
- 测试用例
head = [1,2,3,4,5], k = 2- 题目分类
- 链表
- 解法对比
- 2
分组存数组
每次收集 k 个节点，足够时逆序连接，不足保持原样。
- 时间
O(n)- 空间
O(k)
定位组尾并原地翻转
先确认本组有 k 个节点，再用标准链表反转连接。
- 时间
O(n)- 空间
O(1)