LeetCode 筆記 - 83. Remove Duplicates from Sorted List

Posted on

題目在此 83. Remove Duplicates from Sorted List

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

解題思維

這題其實很簡單，因為鏈結串列是排序過的，所以重複的節點一定是相鄰的。

為簡化邏輯，在這裡使用雙指標法，一個指標 node 用來遍歷整個鏈結串列，另一個指標 pre_node 用來記錄最後一個不重複的節點。

看到不重複的節點時，就將 pre_node.next 指向 node，並且更新 pre_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
# 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: walk all the nodes
        # step 2: skip the duplicate node

        if not head:
            return None

        node = head
        pre_node = head

        while node:

            if pre_node.val != node.val:
                pre_node.next = node
                pre_node = pre_node.next

            node = node.next

        pre_node.next = None

        return head

也許你也會想看看