1 題目描述


給定一個鍊錶，將鍊錶向右旋轉 k 步，其中 k 是非負數。

2 解法

看到這個題目的時候，有想到如果今天k很大，這個linked list多少步驟會回到原本的樣子？基本上是當 k 是 鍊錶長度的倍數時，鍊錶會回到原本的樣子，因此我們可以先計算出鍊錶的長度，然後取餘數，這樣就可以得到我們要旋轉的步數。

當last.next是空的時候，表示觸底

1
2
3
4
5
6
7
8
# 先計算長度
last, count = head, 1
while (last.next): 
    count += 1 
    last = last.next

# 重新計算k取餘數
k = k % count


接下來如果k是2，代表最後面的兩個node會被擠到最前面，因此我們主要有兩個步驟：

  1. 找到last，把last跟head連接起來
  2. 找到新的head，把新head的前一個node的next設為None
1
2
3
4
5
6
7
8
9
10
# 找到last，把last跟head連接起來
last.next = head
# 找到新head的前一個node （從上圖例子為4)
tmp = head
for _ in range(count - k - 1):
    tmp = tmp.next

# 把新head的前一個node的next設為None
new_head = tmp.next
tmp.next = None

完整程式碼為

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    """
    Time: O(n)
    Space: O(1)
    """
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or k == 0 or head.next is None:
            return head
        # 先計算長度
        last, count = head, 1
        while (last.next): 
            count += 1 
            last = last.next
        # 重新計算 k
        k = k % count 
        # 因為 tmp 會更動到 head 所以先處理 last.next 
        last.next = head 
        tmp = head
        # tmp 是要切斷當 head 的節點
        for i in range(count - k - 1):
            tmp = tmp.next 

        # 重新串起來
        ans = tmp.next
        tmp.next = None 
        return ans

3 總結

這題我想了一個小時，我沒有發現 len - k - 1 的方便邏輯，原始方法是透過兩個指標slow, fast去找倒數第k個。這題的重點是要先計算長度，然後取餘數，最後再重新串起來。這題的時間複雜度是 O(n)，空間複雜度是 O(1)。