c++算法進階刪除有序鏈表中的重復元素

更新時間：2023年12月06日 11:22:48 作者：吳尼瑪

這篇文章主要為大家介紹了c++算法進階刪除有序鏈表中的重復元素示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

題目

給出一個升序排序的鏈表，刪除鏈表中的所有重復出現的元素，只保留原鏈表中只出現一次的元素。

例如：

給出的鏈表為1→2→3→3→4→4→5, 返回1→2→5。

給出的鏈表為1→1→1→2→3, 返回2→3。

數據范圍：鏈表長度0≤n≤10000，鏈表中的值滿足∣val∣≤1000

要求：空間復雜度O(n)，時間復雜度O(n)

進階：空間復雜度O(1)，時間復雜度O(n)

示例

示例1

輸入：
{1,2,2}
返回值：
{1}

示例2

輸入：
{}
返回值：
{}

思路

因為是升序的鏈表，重復的元素時連在一起的，所以可以連續(xù)的跳過相同的節(jié)點。

這里有個小技巧：因為鏈表有可能前幾個元素就是重復的，這時就需要刪除頭指針了，所以我們需要給鏈表增加一個自定義的表頭，以方便后面刪除了原來的頭指針而找不到表頭，還有需要注意的就是在返回的時候要去掉增加的表頭。

這種解法的空間復雜度是O(1)，另外也可以通過哈希表unordered_map來記錄每個節(jié)點值出現的次數來解決這個問題。哈希表的方式空間復雜度就是O(n)了，如果鏈表的無序的，則哈希表的解決方法更通用。

解答代碼

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * @param head ListNode類 
     * @return ListNode類
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if (head == nullptr) {
            return nullptr;
        }
        // 給鏈表增加一個表頭，以便可以刪除原鏈表的頭結點。
        auto res = new ListNode(0);
        res->next = head;
        auto cur = res;
        while (cur->next != nullptr && cur->next->next != nullptr) {
            if (cur->next->val == cur->next->next->val) {
                int val = cur->next->val;
                // 跳過所有相同的值
                while (cur->next != nullptr && cur->next->val == val) {
                    cur->next = cur->next->next;
                }
            } else {
                cur = cur->next;
            }
        }
        // 返回值需要去掉增加的表頭
        return res->next;
    }
};

以上就是c++算法進階刪除有序鏈表中的重復元素的詳細內容，更多關于c++刪除有序鏈表重復元素的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: