LeetCode 旋轉鏈表：成環雙指針 O(n) 時間 O(1) 空間

題目描述

給定單鏈表頭節點和整數 k，將鏈表向右旋轉 k 位。k 可能極大，要求不使用額外空間。

範例：

輸入: 1→2→3→4→5→NULL, k = 2
輸出: 4→5→1→2→3→NULL

解題思路：首尾相連成環 + 斷開

1. 遍歷鏈表得長度 len，同時將尾節點 next 指向頭節點（成環）
2. 實際旋轉步數 k %= len，新頭節點為原鏈表第 len - k 個節點
3. 從頭移動 len - k 步到達新尾節點，斷開環（next = nullptr），返回新頭

時間複雜度：O(n)，空間複雜度：O(1)。

Python 參考實現

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def myprint(self):
        print(self.val, end='')
        if self.next:
            print('→', end='')
            self.next.myprint()

class Solution:
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return None
        
        # 計算長度並成環
        curr = head
        length = 1
        while curr.next:
            curr = curr.next
            length += 1
        curr.next = head  # 成環
        
        # 找新尾節點（第 length - k%length 個）
        steps = length - k % length
        new_tail = head
        for _ in range(steps - 1):
            new_tail = new_tail.next
        
        new_head = new_tail.next
        new_tail.next = None  # 斷環
        return new_head

# 測試
if __name__ == "__main__":
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l5 = ListNode(5)
    l1.next = l2; l2.next = l3; l3.next = l4; l4.next = l5
    
    result = Solution().rotateRight(l1, 2)
    result.myprint()  # 輸出: 4→5→1→2→3
    print()

核心要點總結

• 成環技巧：將線性鏈表變為環，旋轉轉化為「移動斷開點」
• 取模優化：k %= len 處理極大 k，避免多輪無效旋轉
• 新頭位置：第 len - k 個節點（0-indexed 為 len - k - 1 步）
• 斷環必要：必須 new_tail.next = nullptr，否則死循環

旋轉鏈表是「成環 + 雙指針」經典模式，同技巧適用於「鏈表右移/左移」、「環形鏈表入口檢測」等問題。