LeetCode 筆記 - 61. Rotate List

Posted on

題目在此 61. Rotate List

給一個 Linked list 與 k，請移動 k 個 node 到最前面

解題思維

這題你可以塞進 list 來操作，但我覺得就是少了點味道

所以還是寫了操作 Linked list 的版本

比較關鍵的地方可能是
移動到最終會變成開頭的 node 前一個 node，找到了新的開頭
前一個 node 也是會變成最後一個，所以給了一個 None

然後原始的最後一個 node 接上，原始的第一個 node

完成

程式碼

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
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        size = 0
        current_node = end = head
        while current_node:
            end = current_node
            current_node = current_node.next
            size += 1
        
        if size <= 1:
            return head
        
        k %= size
        if k == 0:
            return head
        
        current_node = head
        for _ in range(size - k - 1):
            current_node = current_node.next
        
        new_head = current_node.next
        current_node.next = None
        end.next = head
        
        return new_head

相關文章