LeetCode中如何刪除排序鏈表中的重復元素

給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現一次。

示例 1：

• 輸入: 1->1->2
• 輸出: 1->2

示例 2：

• 輸入: 1->1->2->3->3
• 輸出: 1->2->3

二、解題思路

本題考查的是對鏈表的基礎指針操作，只要在遍歷鏈表的同時找到要刪除的節點指針，然后刪除即可，步驟如下：

• 對鏈表的頭結點副本 current 進行遍歷
• 循環遍歷直到到最后一個節點
• 每次遍歷判斷當前節點值是否等于下一節點值
• 如果相等則刪除下一節點
• 如果不等則繼續遍歷下一節點
• 最終返回鏈表頭結點

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 0. 空鏈表返回 nullptr
        if (head == nullptr)
            return nullptr;

        // 1. 不對頭指針操作，頭指針用于返回結果
        ListNode *cur = head;
        ListNode *del_node = nullptr;

        while (current->next != nullptr) {
            // 2. 找到元素相同的節點
            if (cur->val == cur->next->val) {
                // 3. 保存待刪除的節點
                del_node = cur->next;
                
                // 4. 斷開 del_node 節點
                cur->next = del_node->next;
                
                // 5. 刪除節點
                delete del_node;

                // 6. 編程規范：防止出現野指針
                del_node = nullptr;
            } else {
                // 7. 沒找到相同元素就繼續向后遍歷
                cur = cur->next;
            }
        } 

        return head;
    }
};

復雜度分析

• 時間復雜度：O(n)，只需要一次遍歷 n 個鏈表節點
• 空間復雜度：O(1)，只使用常數的內存指針單位