LeetCode中如何刪除排序鏈表中的重復(fù)元素

給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。

示例 1：

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

示例 2：

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

二、解題思路

本題考查的是對(duì)鏈表的基礎(chǔ)指針操作，只要在遍歷鏈表的同時(shí)找到要?jiǎng)h除的節(jié)點(diǎn)指針，然后刪除即可，步驟如下：

• 對(duì)鏈表的頭結(jié)點(diǎn)副本 current 進(jìn)行遍歷
• 循環(huán)遍歷直到到最后一個(gè)節(jié)點(diǎn)
• 每次遍歷判斷當(dāng)前節(jié)點(diǎn)值是否等于下一節(jié)點(diǎn)值
• 如果相等則刪除下一節(jié)點(diǎn)
• 如果不等則繼續(xù)遍歷下一節(jié)點(diǎn)
• 最終返回鏈表頭結(jié)點(diǎn)

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

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

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

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

        return head;
    }
};

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，只需要一次遍歷 n 個(gè)鏈表節(jié)點(diǎn)
• 空間復(fù)雜度：O(1)，只使用常數(shù)的內(nèi)存指針單位