Leetcode 107 旋转链表

1 题目

61. 旋转链表

给你一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4输出：[2,0,1]

提示：

• 链表中节点的数目在范围[0, 500]内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

2 代码实现

c++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (head == nullptr || head -> next == nullptr || k == 0 ){ return head ; } int n = 1; ListNode* tail = head ; while (tail -> next != nullptr){ tail = tail -> next ; n++; } int step = k % n ; if (step == 0 ){ return head ; } tail -> next = head ; ListNode* new_tail = head ; for (int i = 0 ; i < n - step - 1 ; ++i){ new_tail = new_tail -> next ; } ListNode* new_head = new_tail -> next ; new_tail -> next = nullptr ; return new_head; } };

js

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var rotateRight = function(head, k) { if (head == null || head.next == null || k == 0){ return head ; } let n = 1 ; let tail = head ; while(tail.next != null){ tail = tail.next ; n++; } tail.next = head ; let step = k % n ; let new_tail = head ; for(let i = 0 ; i < n - step - 1 ; i++){ new_tail = new_tail.next ; } const new_head = new_tail.next ; new_tail.next = null ; return new_head; };

思考

这道题目我觉得k就是一个“旋转”操作的执行次数，比较难的地方就是尾部的结点要怎么又接回来。

我大概的思路就是建立一个虚拟头结点dummy，cur从head 出发 ，然后dummy -> next = cur -> next ；这么一直往后“旋转”连接，直到cur -> next 是空的了，再把原来的头结点接回来？

不知道怎么写，需要看看cpp实现的题解，我怎么想都觉得这个新的head写法有点麻烦。

题解

解题思路分析

首先要明确一个关键点：如果链表长度为n，那么向右移动k个位置等价于向右移动k % n个位置（因为移动n个位置后链表会回到原样）。这能避免k过大时的无效操作。

解决这个问题的核心步骤：

1. 处理特殊情况（空链表、k=0、链表只有 1 个节点），直接返回原链表；
2. 遍历链表，统计节点总数n，同时找到链表的尾节点；
3. 计算有效移动步数step = k % n，如果step=0直接返回原链表；
4. 将链表首尾相连，形成环形链表；
5. 找到新的尾节点（原链表的第n-step个节点），断开环形链表，新的头节点就是尾节点的下一个节点。

C++ 完整实现代码

#include <iostream> using namespace std; // 定义链表节点结构 struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* rotateRight(ListNode* head, int k) { // 特殊情况：空链表、只有一个节点、k=0，直接返回原链表 if (head == nullptr || head->next == nullptr || k == 0) { return head; } // 第一步：统计链表节点数n，并找到尾节点tail int n = 1; // 至少有一个节点（head非空） ListNode* tail = head; while (tail->next != nullptr) { tail = tail->next; n++; } // 第二步：计算有效移动步数（k可能远大于n） int step = k % n; if (step == 0) { // 移动n的倍数，链表不变 return head; } // 第三步：将链表连成环形（尾节点指向头节点） tail->next = head; // 第四步：找到新的尾节点（距离原头节点n-step-1步） ListNode* new_tail = head; for (int i = 0; i < n - step - 1; i++) { new_tail = new_tail->next; } // 第五步：新的头节点是新尾节点的下一个节点，断开环形链表 ListNode* new_head = new_tail->next; new_tail->next = nullptr; return new_head; } }; // 辅助函数：打印链表 void printList(ListNode* head) { while (head != nullptr) { cout << head->val << " "; head = head->next; } cout << endl; } // 测试用例 int main() { // 示例1：head = [1,2,3,4,5], k=2 ListNode* head1 = new ListNode(1); head1->next = new ListNode(2); head1->next->next = new ListNode(3); head1->next->next->next = new ListNode(4); head1->next->next->next->next = new ListNode(5); Solution s; ListNode* res1 = s.rotateRight(head1, 2); cout << "示例1输出："; printList(res1); // 预期输出：4 5 1 2 3 // 示例2：head = [0,1,2], k=4 ListNode* head2 = new ListNode(0); head2->next = new ListNode(1); head2->next->next = new ListNode(2); ListNode* res2 = s.rotateRight(head2, 4); cout << "示例2输出："; printList(res2); // 预期输出：2 0 1 return 0; }

代码关键部分解释

1. 特殊情况处理：避免无意义的计算，比如空链表、单节点链表无需旋转，直接返回；
2. 统计节点数 + 找尾节点：这一步是为了后续计算有效步数，同时为连成环形链表做准备；
3. 有效步数计算：k % n是核心优化，比如示例 2 中k=4、n=3，有效步数是1（4%3=1），等价于向右移动 1 个位置；
4. 环形链表处理：将尾节点指向头节点，这样旋转时无需反复遍历，只需找到新的头尾节点即可；
5. 找新的头尾节点：
   • 新尾节点位置：原链表的第n-step-1个节点（比如示例 1 中n=5、step=2，新尾节点是第5-2-1=2个节点，即值为 3 的节点）；
   • 新头节点是新尾节点的下一个节点（示例 1 中是 4），最后断开环形链表（新尾节点的 next 置空）。

总结

1. 核心优化点：用k % n减少无效旋转，避免k过大时的性能问题；
2. 关键技巧：将链表连成环形，通过找节点位置直接确定新的头尾，无需逐次旋转；
3. 步骤逻辑：统计长度→算有效步数→连环形→找新头尾→断环形。

这种方法的时间复杂度是 O (n)（只遍历链表两次），空间复杂度是 O (1)（只使用了几个指针变量），是最优的解法。

3 小结

变成环形以后再求解，然后断链，我觉得虽然我们走测试用例的时候是这么想的，但我实际却没有用这样成环又断链的办法在做，见多识广吧，我个人感受是见过这个做法就知道，没见过就不知道，会者不难，难者不会，也不必太担忧。

1. 先统计长度是链表题的常见套路很多链表题目，只要涉及 “旋转”“倒数第 k 个”“环” 等，都需要先知道链表长度，这一步往往能带来后续的巨大简化。

2. k 可能非常大，必须用 k % n 来减少无效操作题目给的 k 可以达到 2×10^9，如果不做取模，直接模拟肯定超时。取模后问题规模瞬间缩小到链表长度范围内。

3. 成环操作让 “旋转” 变成了 “找节点 + 断链”把链表首尾相连后，旋转 k 次等价于在环中找到新的尾节点，然后断开环。这个思路非常巧妙，也非常高效。

4. 新尾节点的位置公式 n - step - 1 是关键理解这个公式的推导过程后，整个题就变得非常清晰：新尾节点就是原链表中 “倒数第 step+1 个节点”。