解LeetCode的學習筆記Day25_Reverse Nodes in k-Group

#leetcode #學習筆記

LFI 2025-10-16 21:38:13 ‧ 155 瀏覽

分享至

今天是紀錄LeetCode解題的第二十五天
是一題困難題

第二十五題題目：Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

給定一個鏈結串列，一次反轉k個節點，回傳修改後的鏈結串列
k是一個正整數，且小於或等於鏈結串列長度，如果節點不是k的倍數，則回傳剩餘的節點
不可以修改節點的值，只能改變節點本身

解題思路

先找k個節點，tail指向該組節點的最後一個節點，接著進行反轉節點

變數意義

變數名稱	意義與作用
`dummy`	虛擬頭節點，指向整條鏈結串列的開頭
`prev`	指向「上一組反轉後的尾巴」
`tail`	每次用來尋找當前要反轉的這一組的「尾巴節點」，確定是否有足夠 k 個節點
`next_group`	記錄下一組的開頭（即 `tail.next`），反轉完這組後會接回這個節點
`start`	當前這一組的「開頭節點」，反轉之後它會變成這一組的「尾巴」
`cur`	反轉時的游標，從 `start` 開始一路往 `next_group` 前進
`prev_node`	反轉過程中指向當前 `cur` 節點要接上的「前一個節點」，一開始是 `next_group`
`tmp`	暫存 `cur.next`，確保反轉時不會丟失後續節點

程式碼

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while True:
            tail = prev
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next

            next_group = tail.next

            start = prev.next
            prev_node = tail.next
            cur = prev.next
            while cur != next_group:
                tmp = cur.next
                cur.next = prev_node
                prev_node = cur
                cur = tmp
            prev.next = tail
            prev = start