LeetCode 筆記 - 83. Remove Duplicates from Sorted List

介紹移除排序鏈結串列中重複節點的基本操作。本文透過單次遍歷與相鄰節點比對，簡單明瞭地去重並保持鏈結結構，是學習鏈結串列 (Linked List) 指標跳轉技術的入門必備練習。

發佈: 2024.10.01
閱讀: 約 1 分鐘
字數: 259

題目在此 83. Remove Duplicates from Sorted List

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

解題思維

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

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

看到不重複的節點時，就將 pre_node.next 指向 node，並且更新 pre_node 為 node。

程式碼

# 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

也許你也會想看看