LeetCode 筆記 - 82. Remove Duplicates from Sorted List II

Posted on

題目在此 82. Remove Duplicates from Sorted List II

給定一個排序過的鏈結串列，請移除所有重複的節點，並且回傳新的鏈結串列。

解題思維

這是 Remove Duplicates from Sorted List 系列的第二題了，如果沒解過第一題可以先看看這裡:
LeetCode 筆記 - 83. Remove Duplicates from Sorted List

這題的難點是要移除所有重複的節點，而不是只保留一個，所以這題會到經典解法 dummy node，來簡化邏輯。

先建立一個 dummy 節點，並且將 dummy.next 指向 head，如此一來就可以避免處理 head 節點被刪除的特殊情況。

接著使用雙指標法，一個指標 node 用來遍歷整個鏈結串列，另一個指標 pre_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
32
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # step 1: create a dummy head, to avoid the real head is duplicate
        # step 2: if node.next exists and node.val == node.next.val, skip the duplicate nodes
        # otherwise, add to result linked list

        dummy = ListNode(0, head)
        
        node = head
        pre_node = dummy

        while node:

            if node.next and node.val == node.next.val:
                while node.next and node.val == node.next.val:
                    node = node.next

                # run until the end of the duplicate list.
                # the next one is probability the one of result

            else:
                pre_node.next = node
                pre_node = pre_node.next

            node = node.next

        pre_node.next = None
        return dummy.next

也許你也會想看看