0061.旋转链表

张开发
• 2026/4/9 1:03:10 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

0061.旋转链表
题目链接https://leetcode.cn/problems/rotate-list/题目描述给定单链表 head 和整数 k将链表向右旋转 k 位并返回旋转后的链表。解题思路闭环 定位新尾先计算链表长度 cnt并找到尾节点 tail。实际旋转步数为 k % cnt。若为 0直接返回 head。将链表首尾相连变成环tail.next head。新的头节点是从原头节点向右移动 k % cnt 位也等价为从尾节点出发向前走 cnt - (k % cnt) 步后的下一个节点。遍历 leftCnt cnt - k % cnt 步停在新尾节点 newTail。新头节点 newHead newTail.next断开环 newTail.next null。题解代码classSolution{publicListNoderotateRight(ListNodehead,intk){if(k0||headnull||head.nextnull){returnhead;}// 1) 计算链表长度并定位尾节点intcnt1;ListNodecurhead;while(cur.next!null){cnt;curcur.next;}// 2) 取模优化k 可能远大于长度intshiftk%cnt;if(shift0)returnhead;// 3) 首尾相连成环cur.nexthead;// 4) 走到新尾节点其后一个就是新头intleftCntcnt-shift;while(leftCnt--0){curcur.next;}// 5) 断开环形成新链表ListNodenewHeadcur.next;cur.nextnull;returnnewHead;}}边界与注意事项k 可能非常大务必先取模。当链表长度为 1 或 k 为 0 时直接返回可避免不必要操作。将链表连成环后务必在返回前断开否则会造成环形链表。复杂度分析时间复杂度O(n)单次遍历计算长度 单次定位新尾总体线性。空间复杂度O(1)仅使用常数级指针变量。

更多文章