旋转链表 图解题解
k 可能比链表还长——先成环再一刀切，两趟走完搞定旋转。
旋转一条项链 k 格，与其一颗颗挪 k 次，不如先把首尾接成环，再找准断点剪开。做法分两趟：第一趟从头走到尾巴数出长度 n，顺手把尾接回头成环；k 对 n 取余得到真正要挪的格数，再从头走 n−(k%n)−1 步停下，这个节点就是新尾，下一个就是新头，最后在这里把环剪断。
这道题到底在问什么
- 输入
- head=[1,2,3,4,5,6,7,8,9], k=3
- 输出
- [7,8,9,1,2,3,4,5,6]
最优解：一步一步想明白
- 3为什么要 k%n？k 可能比 n 大，右移 n 位等于没移，所以真正的位移是 k 对 n 取模。下面一步步演示。
- 4先用指针 p 走一遍链表，边走边数长度 n。现在 p 在头节点 1，n=1。
- 5p 向后挪一格到值 2，长度计数 n=2。继续往后走直到 next 为 null。
- 6p 向后挪一格到值 3，长度计数 n=3。继续往后走直到 next 为 null。
- 7p 向后挪一格到值 4，长度计数 n=4。继续往后走直到 next 为 null。
- 8p 向后挪一格到值 5，长度计数 n=5。继续往后走直到 next 为 null。
- 9p 向后挪一格到值 6，长度计数 n=6。继续往后走直到 next 为 null。
- 10p 向后挪一格到值 7，长度计数 n=7。继续往后走直到 next 为 null。
- 11p 向后挪一格到值 8，长度计数 n=8。继续往后走直到 next 为 null。
- 12p 走到值 9，它的 next 是 null —— 这就是表尾。一路数下来 n=9。记住尾节点，下一步要用它接环。
- 13长度 n=9，k=3。真正要移的位数 = k%n = 3%9 = 3。尾节点（值 9）已点亮，接下来把它接回头节点成环。
- 14把尾节点 9 的 next 接回头节点 1（尾部出现「↺ 回到 1」）。整条链先连成一个环，这样从任意点断开都能重排顺序。
- 15要在「新尾」后面断开。新尾 = 从头往后走 n−k%n = 9−3 = 6 步。q 先站在头节点 1（这是第 1 个，还需再走 5 步）。
- 16q 向后挪一格到值 2（已走 2 步）。继续走够 6 步。
- 17q 向后挪一格到值 3（已走 3 步）。继续走够 6 步。
- 18q 向后挪一格到值 4（已走 4 步）。继续走够 6 步。
- 19q 向后挪一格到值 5（已走 5 步）。继续走够 6 步。
- 20q 共走了 6 步，停在值 6 —— 这就是「新尾」（断开后链表的最后一个）。它的下一个节点 7 将成为新头。
- 21新尾 = 6，它后面的 7 就是新头。马上做两件事：新头 = 新尾.next；新尾.next = null。环会在这里被打断。
- 22把新尾 6 指向 7 的箭头断成 ·（即 6.next = null）。此刻原尾 9 还接着头 1（环未拆），但新链的末尾已经定下。
- 23环解除：原来「尾 9 → 头 1」的那根回边，现在成了新链中间的普通连接（9 后面接 1）。新头是 7，新尾是 6。
- 24上行是物理链（节点没动，只是断点改了）；下行是顺着新头 7 读出的逻辑顺序 7→8→9→1→2→3→4→5→6。这正是右移 3 位的结果，返回新头 7。
⚠️ 容易写错的地方
✗ 错：忘记 k %= n
✓ 对：必须先对 n 取模
k 可能远大于 n，右移 n 位等于没动，不取模会白走甚至越界
✗ 错：新尾走了 n-k 步（多一步）
✓ 对：从头走 n−k−1 步到新尾
头算第 1 个，走 n−k−1 步正好停在第 n−k 个节点上
✗ 错：忘了把新尾.next 置空
✓ 对：断开前必须 newTail.next = null
不断开就还是个环，顺着走会无限循环
完整代码（Python / C++ / Java）
Python
def rotateRight(head, k):
if not head or not head.next or k == 0:
return head
# ① 走到尾、数长度 n
n, tail = 1, head
while tail.next:
tail = tail.next; n += 1
k %= n # ② k 对 n 取模
if k == 0: return head
tail.next = head # ③ 尾连头成环
# ④ 从头走 n-k 步到新尾
newTail = head
for _ in range(n - k - 1):
newTail = newTail.next
newHead = newTail.next
newTail.next = None # 断开成新链
return newHeadC++
ListNode* rotateRight(ListNode* head, int k){
if(!head || !head->next || k==0) return head;
int n = 1; ListNode* tail = head;
while(tail->next){ tail = tail->next; n++; }
k %= n;
if(k == 0) return head;
tail->next = head; // 成环
ListNode* newTail = head;
for(int i = 0; i < n-k-1; i++)
newTail = newTail->next;
ListNode* newHead = newTail->next;
newTail->next = nullptr; // 断开
return newHead;
}Java
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) { tail = tail.next; n++; }
k %= n;
if (k == 0) return head;
tail.next = head; // 成环
ListNode newTail = head;
for (int i = 0; i < n - k - 1; i++)
newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null; // 断开
return newHead;复杂度
时间
O(n)
数长度走一遍 + 找新尾走 n−k 步，合计线性
空间
O(1)
只用 tail / newTail / newHead 几个指针，原地改链
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 旋转链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么先成环再断，而不是直接找两段拼接？+
成环后只需定位一个「新尾」就能一次断开重排，逻辑统一；不成环则要分别处理尾接头、找断点两件事，更易错。
左移 k 位怎么改？+
左移 k 等于右移 n−k。同样成环，新尾改成从头走 k−1 步（即第 k 个节点）后断开即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 旋转链表 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。