核心内容摘要
《91黑料》：信息洪流中的真相与迷雾_1_3
1 题目
旋转链表给你一个链表的头节点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 1000 k 2 * 1092 代码实现c/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(
, 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 (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode} head * param {number} k * return {ListNode} */ var rotateRight function(head, k) { if (head null || head.next null || k
{ 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就是一个“旋转”操作的执行次数比较难的地方就是尾部的结点要怎么又接回来。
我大概的思路就是建立一个虚拟头结点dummycur从head 出发 然后dummy - next cur - next 这么一直往后“旋转”连接直到cur - next 是空的了再把原来的头结点接回来不知道怎么写需要看看cpp实现的题解我怎么想都觉得这个新的head写法有点麻烦。
题解解题思路分析首先要明确一个关键点如果链表长度为n那么向右移动k个位置等价于向右移动k % n个位置因为移动n个位置后链表会回到原样。
这能避免k过大时的无效操作。
解决这个问题的核心步骤处理特殊情况空链表、k
链表只有 1 个节点直接返回原链表遍历链表统计节点总数n同时找到链表的尾节点计算有效移动步数step k % n如果step0直接返回原链表将链表首尾相连形成环形链表找到新的尾节点原链表的第n-step个节点断开环形链表新的头节点就是尾节点的下一个节点。
C 完整实现代码#include iostream using namespace std; // 定义链表节点结构 struct ListNode { int val; ListNode *next; ListNode() : val(
, 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) { // 特殊情况空链表、只有一个节点、k0直接返回原链表 if (head nullptr || head-next nullptr || k
{ 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
{ // 移动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() { // 示例1head [1,2,3,4,5], k2 ListNode* head1 new ListNode(
; head1-next new ListNode(
; head1-next-next new ListNode(
; head1-next-next-next new ListNode(
; head1-next-next-next-next new ListNode(
; Solution s; ListNode* res1 s.rotateRight(head1,
; cout 示例1输出; printList(res
; // 预期输出4 5 1 2 3 // 示例2head [0,1,2], k4 ListNode* head2 new ListNode(
; head2-next new ListNode(
; head2-next-next new ListNode(
; ListNode* res2 s.rotateRight(head2,
; cout 示例2输出; printList(res
; // 预期输出2 0 1 return 0; }代码关键部分解释特殊情况处理避免无意义的计算比如空链表、单节点链表无需旋转直接返回统计节点数 找尾节点这一步是为了后续计算有效步数同时为连成环形链表做准备有效步数计算k % n是核心优化比如示例 2 中k
n3有效步数是14%31等价于向右移动 1 个位置环形链表处理将尾节点指向头节点这样旋转时无需反复遍历只需找到新的头尾节点即可找新的头尾节点新尾节点位置原链表的第n-step-1个节点比如示例 1 中n
step2新尾节点是第
个节点即值为 3 的节点新头节点是新尾节点的下一个节点示例 1 中是 4最后断开环形链表新尾节点的 next 置空。
总结核心优化点用k % n减少无效旋转避免k过大时的性能问题关键技巧将链表连成环形通过找节点位置直接确定新的头尾无需逐次旋转步骤逻辑统计长度→算有效步数→连环形→找新头尾→断环形。
这种方法的时间复杂度是 O (n)只遍历链表两次空间复杂度是 O (
只使用了几个指针变量是最优的解法。
3 小结变成环形以后再求解然后断链我觉得虽然我们走测试用例的时候是这么想的但我实际却没有用这样成环又断链的办法在做见多识广吧我个人感受是见过这个做法就知道没见过就不知道会者不难难者不会也不必太担忧。
先统计长度是链表题的常见套路很多链表题目只要涉及 “旋转”“倒数第 k 个”“环” 等都需要先知道链表长度这一步往往能带来后续的巨大简化。
k 可能非常大必须用 k % n 来减少无效操作题目给的 k 可以达到 2×10^9如果不做取模直接模拟肯定超时。
取模后问题规模瞬间缩小到链表长度范围内。
成环操作让 “旋转” 变成了 “找节点 断链”把链表首尾相连后旋转 k 次等价于在环中找到新的尾节点然后断开环。
这个思路非常巧妙也非常高效。
新尾节点的位置公式 n - step - 1 是关键理解这个公式的推导过程后整个题就变得非常清晰新尾节点就是原链表中 “倒数第 step1 个节点”。