61. Rotate List

Medium

Description

給定一個鏈結串列的頭節點 head，將串列向右旋轉 k 個位置。

Example:

Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]

Intuition#

核心思路：將串列接成環，然後在正確位置斷開。

向右旋轉 k 等於把最後 k 個節點搬到前面
k 可能大於串列長度，需要取餘數
找到新的尾節點（從頭數第 n-k 個），在那裡斷開

Approaches#

1: Find New Tail#

概念: 先算長度並接成環，再找到新的尾節點位置斷開
時間複雜度: O(n)
空間複雜度: 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#

概念: 先讓 fast 走 k 步，然後 fast 和 slow 一起走到尾端，slow 就是新的尾節點
時間複雜度: O(n)
空間複雜度: 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: 旋轉串列本質是找到斷點，然後重新連接。接成環再斷開是優雅的做法
關鍵技巧: k 必須取餘數（k % length），否則會做多餘的旋轉；k == 0 或 k == length 時不需操作