京公网安备11010502063487号给定一个链表的头结点和整数 k，把链表向右旋转 k 个位置：每旋转一位，最后一个结点移到最前面。k 可能远大于链表长度（题目允许到 20 亿），所以先要意识到旋转 n 次（n 是链表长度）等于没转，k 只需要对 n 取模。做法是：走一遍数出长度并找到尾结点；把尾结点接到头结点上成环；新的尾结点是原来的第 n - k 个结点，新的头结点是它的下一个；在新尾处断开环。本文用真实数据展示漏掉取模的后果，实测这个做法与"每次转一位重复 k 次"的耗时，给出五种语言的实现，并把找断点的过程做成分步演示。
完整题目见官方页面（链接在文末）。链表在测试里用整数数组表示，旋转之后的结果也用数组表示。基准解直接在数组上切片：把最后 k 个元素移到最前面（k 先对长度取模），与指针成环的做法是两种独立的写法。一共 13 组用例，覆盖：官方示例、空链表、单个结点、k 等于 0、k 等于链表长度、k 大于链表长度、k 高达 19 亿 9999 万多：
输入 [[1,2,3,4,5],2] 输出 [4,5,1,2,3] 输入 [[0,1,2],4] 输出 [2,0,1] 输入 [[],3] 输出 [] 输入 [[1],5] 输出 [1] 输入 [[1,2],0] 输出 [1,2] 输入 [[1,2],1] 输出 [2,1]
新的尾结点是第 n - k 个结点，如果 k 大于 n，n - k 是负数，循环一次都不走，得到的位置是错的。就算 k 恰好等于 n（旋转一整圈，应该原样返回），不取模的写法也会转错。下面是不取模的写法与 solve 的真实结果：
# 没有 k %= n 的写法 [1, 2, 3, 4, 5], k=2: 不取模 -> [4, 5, 1, 2, 3] solve -> [4, 5, 1, 2, 3] [0, 1, 2], k=4: 不取模 -> [1, 2, 0] solve -> [2, 0, 1] [1, 2], k=3: 不取模 -> [2, 1] solve -> [2, 1] [1, 2, 3, 4, 5], k=5: 不取模 -> [2, 3, 4, 5, 1] solve -> [1, 2, 3, 4, 5] [1, 2, 3, 4, 5], k=7: 不取模 -> [2, 3, 4, 5, 1] solve -> [4, 5, 1, 2, 3]
[1, 2, 3, 4, 5] 在 k = 2 时两种写法都对，因为 k 没超过 n；k = 4（n = 3）、k = 5（n = 5）、k = 7（n = 5）都答错，例如 [1, 2, 3, 4, 5] 转 5 位应该是原样，不取模的写法得到 [2, 3, 4, 5, 1]。[1, 2] 转 3 位的一行两种写法碰巧一致（n - k - 1 是负数，循环没有执行，恰好停在了正确的位置），这是巧合，不能据此认为不取模没有问题。
先走一遍链表数出长度 n 并找到尾结点；k %= n，为 0 就直接返回原链表；否则把尾结点的 next 指向头结点，形成环；从头结点走 n - k - 1 步，到达新的尾结点，它的下一个就是新的头结点；把新尾结点的 next 置空，环就断开了，返回新的头结点。空链表和只有一个结点的链表在最前面单独处理。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def rotate_right(head, k): if not head or not head.next or k == 0: return head n, tail = 1, head while tail.next: # 走一遍：数出长度 n，并找到尾结点 tail = tail.next n += 1 k %= n # 旋转 n 次等于没转：先取模 if k == 0: return head tail.next = head # 首尾相连成环 new_tail = head for _ in range(n - k - 1): # 新的尾结点是原来的第 n-k 个结点 new_tail = new_tail.next new_head = new_tail.next new_tail.next = None # 在新尾处断开 return new_head
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3,4,5],2] → [4,5,1,2,3] [[0,1,2],4] → [2,0,1] [[],3] → [] [[1],5] → [1] [[1,2],0] → [1,2] [[1,2],1] → [2,1]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int n = 1; ListNode tail = head; while (tail.next != null) { // 走一遍：数出长度 n，并找到尾结点 tail = tail.next; n++; } k %= n; // 旋转 n 次等于没转：先取模 if (k == 0) return head; tail.next = head; // 首尾相连成环 ListNode newTail = head; for (int i = 0; i < n - k - 1; i++) newTail = newTail.next; // 新的尾结点是原来的第 n-k 个结点 ListNode newHead = newTail.next; newTail.next = null; // 在新尾处断开 return newHead; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3,4,5],2] → [4,5,1,2,3] [[0,1,2],4] → [2,0,1] [[],3] → [] [[1],5] → [1] [[1,2],0] → [1,2] [[1,2],1] → [2,1]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func rotateRight(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil || k == 0 { return head } n, tail := 1, head for tail.Next != nil { // 走一遍：数出长度 n，并找到尾结点 tail = tail.Next n++ } k %= n // 旋转 n 次等于没转：先取模 if k == 0 { return head } tail.Next = head // 首尾相连成环 newTail := head for i := 0; i < n-k-1; i++ { // 新的尾结点是原来的第 n-k 个结点 newTail = newTail.Next } newHead := newTail.Next newTail.Next = nil // 在新尾处断开 return newHead }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3,4,5],2] → [4,5,1,2,3] [[0,1,2],4] → [2,0,1] [[],3] → [] [[1],5] → [1] [[1,2],0] → [1,2] [[1,2],1] → [2,1]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function rotateRight(head, k) { if (!head || !head.next || k === 0) return head; let n = 1, tail = head; while (tail.next) { // 走一遍：数出长度 n，并找到尾结点 tail = tail.next; n++; } k %= n; // 旋转 n 次等于没转：先取模 if (k === 0) return head; tail.next = head; // 首尾相连成环 let newTail = head; for (let i = 0; i < n - k - 1; i++) newTail = newTail.next; // 新的尾结点是原来的第 n-k 个结点 const newHead = newTail.next; newTail.next = null; // 在新尾处断开 return newHead; }
$ node run.js < cases.jsonl [[1,2,3,4,5],2] → [4,5,1,2,3] [[0,1,2],4] → [2,0,1] [[],3] → [] [[1],5] → [1] [[1,2],0] → [1,2] [[1,2],1] → [2,1]
C++ · 解法代码struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (!head || !head->next || k == 0) return head; int n = 1; ListNode* tail = head; while (tail->next) { // 走一遍：数出长度 n，并找到尾结点 tail = tail->next; n++; } k %= n; // 旋转 n 次等于没转：先取模 if (k == 0) return head; tail->next = head; // 首尾相连成环 ListNode* newTail = head; for (int i = 0; i < n - k - 1; i++) newTail = newTail->next; // 新的尾结点是原来的第 n-k 个结点 ListNode* newHead = newTail->next; newTail->next = nullptr; // 在新尾处断开 return newHead; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3,4,5],2] → [4,5,1,2,3] [[0,1,2],4] → [2,0,1] [[],3] → [] [[1],5] → [1] [[1,2],0] → [1,2] [[1,2],1] → [2,1]
共 13 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 13/13 Java 通过 13/13 Go 通过 13/13 JavaScript 通过 13/13 C++ 通过 13/13
如果每次只旋转一位（把最后一个结点摘下来放到头部），重复 k 次，每次都要走一遍链表找到倒数第二个结点，总共是 O(n × k)。链表长度 1000，k 不同时，与本文解法的真实耗时：
链表长度 1000，k 不同：每次转一格重复 k 次 vs solve（各取三次中最快） k= 1000: 逐格旋转 11.43 ms solve 0.047 ms 结果一致=True k= 5000: 逐格旋转 56.17 ms solve 0.048 ms 结果一致=True k= 20000: 逐格旋转 226.46 ms solve 0.046 ms 结果一致=True
逐格旋转的耗时与 k 成正比：k = 1000 时 11.4ms，k = 5000 时 56.2ms，k = 20000 时 226.5ms；本文解法的耗时约 0.047ms，不随 k 变化，因为 k 只是取模一次。k 达到 20 亿时逐格旋转要几十万秒，没有运行，按线性关系估算，这不是实测。
Python 版本另外和数组切片做了随机对拍：链表长度 0 到 10，k 一半取 0 到 25、一半取 0 到 20 亿：
随机对拍 20000 组（长度 0 到 10 的随机链表，k 一半取 0 到 25、一半取 0 到 20 亿），solve 与 brute 的结果全部一致。
另外四种语言只在上面 13 组固定用例上验证过，其中包含了 k 接近 20 亿的情形，没有做大规模随机对拍。
下面的演示用 [1, 2, 3, 4, 5]、k = 2。长度 5，k % 5 = 2；把尾结点接回头结点成环；新的尾结点是第 5 - 2 = 3 个结点（值 3），新的头结点是它的下一个（值 4）；在值 3 的结点之后断开，得到 [4, 5, 1, 2, 3]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。