65.旋转链表
题目
给你一个链表的头节点 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
思路
向右移动k个位置的意思是: 把链表尾部的k个节点整体挪到前面去。
以[1,2,3,4,5],k=2为例，向右移动2位就是把最后2个节点4，5挪到最前面:
原始: 1 -> 2 -> 3 -> 4 -> 5
最后两个挪到前面
结果: 4 -> 5 -> 1 -> 2 -> 3
换个角度看，其实就是在倒数第k个节点前面断开，然后把后半段接到前半段前面。
这里有几个问题，就是k可能比链表还长。
看第二个例子 [0,1,2], k=4。链表只有 3 个节点，却要向右转 4 次。但你想想：一个长度为 3 的链表，每转 3 次就转回原样了。所以转 4 次 = 转 4 % 3 = 1 次。
结论：真正有效的移动步数是 k % n（n 是链表长度）。如果 k 是 n 的整数倍，那等于没动，直接返回原链表。
所以第一步必须先求出链表长度 n，然后 k = k % n。
核心技巧
-
把链表收尾相连，变成一个环。
-
找到新的断开点，把环断开。
既然要把最后k个节点挪到前面，那么新链表的头就是倒数第k个节点，新链表的尾就是倒数第k+1个节点(也就是新头前面那个)，我们只要在这个位置把环切断就行。
- 那怎么找断点？成环之前我们已经数出长度n，尾结点在位置n，从尾结点再往前走，新的尾结点应该在正数第 n - k 个位置。走到那里，把它的next断开(设为null)，它的原next就是新的头。
用例子走一遍([1,2,3,4,5], k=2, n=5)
- k = 2 % 5 = 2
- 成环: 5指向1
- 新尾在第n - k = 5 - 2 = 3个位置，也就是节点3
- 断开: 节点3的next设为null，新头就是3.next原来指向的节点4 这样就变成了 4 -> 5 -> 1 -> 2 -> 3
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun rotateRight(head: ListNode?, k: Int): ListNode? {
// 1. 边界：空链表或只有一个节点，怎么转都不变
if (head?.next == null) {
return head
}
// 2. 遍历求长度 n，同时让 tail 走到尾节点
var n = 1
var tail: ListNode = head
while (tail.next != null) {
tail = tail.next!!
n++
}
// 3. 计算有效步数；如果 k 是 n 的整数倍，等于没转，直接返回
val steps = k % n
if (steps == 0) {
return head
}
// 4. 尾节点接回头节点，形成环
tail.next = head
// 5. 从头走 n - steps - 1 步，找到新的尾节点
var newTail: ListNode = head
for (i in 0 until n - steps - 1) {
newTail = newTail.next!!
}
// 6. 新头是新尾的下一个；断开环
val newHead: ListNode = newTail.next!!
newTail.next = null
// 7. 返回新头
return newHead
}
}
复杂度
- 时间复杂度: O(n)：第一次遍历求长度走 n 步，第二次找新尾最多走 n 步，整体线性。
- 空间复杂度: O(1)：只用了 tail、newTail、newHead 几个指针，没有额外空间。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!