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(k==0||head==null||head.next==null){returnhead;}// 1) 计算链表长度，并定位尾节点intcnt=1;ListNodecur=head;while(cur.next!=null){cnt++;cur=cur.next;}// 2) 取模优化：k 可能远大于长度intshift=k%cnt;if(shift==0)returnhead;// 3) 首尾相连成环cur.next=head;// 4) 走到新尾节点：其后一个就是新头intleftCnt=cnt-shift;while(leftCnt-->0){cur=cur.next;}// 5) 断开环，形成新链表ListNodenewHead=cur.next;cur.next=null;returnnewHead;}}

边界与注意事项

• k 可能非常大，务必先取模。
• 当链表长度为 1 或 k 为 0 时直接返回，可避免不必要操作。
• 将链表连成环后，务必在返回前断开，否则会造成环形链表。

复杂度分析

• 时间复杂度：O(n)
  • 单次遍历计算长度 + 单次定位新尾，总体线性。
• 空间复杂度：O(1)
  • 仅使用常数级指针变量。