給定一個鏈結串列的頭節點
head，將串列向右旋轉k個位置。
Example:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Intuition
TIP
核心思路：將串列接成環，然後在正確位置斷開。
- 向右旋轉 k 等於把最後 k 個節點搬到前面
- k 可能大於串列長度，需要取餘數
- 找到新的尾節點（從頭數第 n-k 個），在那裡斷開
Approaches
1. Find New Tail — O(n) / O(1)
- Idea: 先算長度並接成環，再找到新的尾節點位置斷開
- Time:
O(n) - Space:
O(1)
class Solution {
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head?.next == null || k == 0) return head
// 計算長度並找到尾節點
var length = 1
var tail = head
while (tail?.next != null) {
length++
tail = tail.next
}
// k 取餘數
val rotate = k % length
if (rotate == 0) return head
// 接成環
tail?.next = head
// 找到新的尾節點（從頭走 length - rotate - 1 步）
var newTail = head
for (i in 0 until length - rotate - 1) {
newTail = newTail?.next
}
// 斷開
val newHead = newTail?.next
newTail?.next = null
return newHead
}
}⭐ 2. Two Pointers — O(n) / O(1)
- Idea: 先讓 fast 走 k 步，然後 fast 和 slow 一起走到尾端，slow 就是新的尾節點
- Time:
O(n) - Space:
O(1)
class Solution {
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head?.next == null || k == 0) return head
// 先計算長度
var length = 0
var curr = head
while (curr != null) {
length++
curr = curr.next
}
val rotate = k % length
if (rotate == 0) return head
// fast 先走 rotate 步
var fast = head
for (i in 0 until rotate) {
fast = fast?.next
}
// slow 和 fast 一起走到尾端
var slow = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next
}
// slow 是新的尾，slow.next 是新的頭
val newHead = slow?.next
slow?.next = null
fast?.next = head
return newHead
}
}🔑 Takeaways
- Pattern: 旋轉串列本質是找到斷點，然後重新連接。接成環再斷開是優雅的做法
- Key trick: k 必須取餘數（k % length），否則會做多餘的旋轉；k == 0 或 k == length 時不需操作