AlgoViz Lab交互式算法学习Algorithms first
旋转链表 · 交互式算法学习
把链表向右轮转 k 个位置。
#61 · 链表
旋转链表
Rotate List
head = [1,2,3,4,5], k = 2链表3 个关键状态
步骤 1计算长度 5，并让尾节点指回头部。
cycle1next
→2next
→3next
→4next
→5next
推荐
成环后切断
时间
O(n)空间 O(1)先首尾相连成环，在新尾部切断。
1function rotateRight(head, k) {2 if (!head || !head.next) return head;3 let n = 1,4 tail = head;5 while (tail.next) {6 tail = tail.next;7 n++;8 }9 k %= n;10 if (!k) return head;11 tail.next = head;12 let newTail = head;13 for (let i = 1; i < n - k; i++) newTail = newTail.next;14 const newHead = newTail.next;15 newTail.next = null;16 return newHead;17}多语言参考
来源 · 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 rotateRight(ListNode head, int k) {13 if (head == null || head.next == null) {14 return head;15 }16 ListNode cur = head;17 int n = 0;18 for (; cur != null; cur = cur.next) {19 n++;20 }21 k %= n;22 if (k == 0) {23 return head;24 }25 ListNode fast = head;26 ListNode slow = head;27 while (k-- > 0) {28 fast = fast.next;29 }30 while (fast.next != null) {31 fast = fast.next;32 slow = slow.next;33 }34 ListNode ans = slow.next;35 slow.next = null;36 fast.next = head;37 return ans;38 }39}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
旋转链表 · 解法对比
把链表向右轮转 k 个位置。
- 测试用例
head = [1,2,3,4,5], k = 2- 题目分类
- 链表
- 解法对比
- 2
重复移动尾节点到头部
每轮找到尾节点及其前驱，把尾节点移到头部。
- 时间
O(kn)- 空间
O(1)
成环后切断
先首尾相连成环，在新尾部切断。
- 时间
O(n)- 空间
O(1)