链表去重

Posted on Edited on Symbols count in article: 2.8k Reading time ≈ 3 mins.

83 删除排序链表中重复元素

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* ptr = head->next;
        while(ptr && head->val == ptr->val) ptr = ptr->next;

        // 下面俩方式效果一样
        head->next = deleteDuplicates(ptr);
        // head->next = ptr;
        // deleteDuplicates(ptr);
        return head;
    }
};

后续遍历

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        // 有点像并查集里的路径压缩
        head->next = deleteDuplicates(head->next);
        if(head->next && head->val == head->next->val)
            return head->next;
        return head;
    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) 
                cur->next = cur->next->next;
            else 
                cur = cur->next;
        }
        return head;
    }
};

迭代法：双指针

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
29
30
31
32
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode* slow = head, *fast = head;
        while(fast){
            if(fast->val != slow->val){
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }
        slow->next = nullptr; // 别忘了
        return head;
    }
};

// 类似于数组去重，一模一样
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[slow] != nums[fast]){
                nums[++slow] = nums[fast];
            }
            ++fast;
        }
        return slow + 1;
    }
};

82 删除排序链表中的重复元素Ⅱ

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int prev = INT_MAX;
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next){
            if(head) prev = head->val;
            return head;
        }
        head->next = deleteDuplicates(head->next);
        while(head && head->val == prev) // 如果要delete，在这里
            head = head->next;
        if(head && head->val < prev) // 小于号很重要，因为是递增链表，防止prev更新旧值
            prev = head->val;
        return head;
    }
};

递归2(类似83后续遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int prev = INT_MIN;
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        // 有点像并查集里的路径压缩
        head->next = deleteDuplicates(head->next);
        if(head->next && head->val == head->next->val){
            prev = head->val;
            return head->next->next;
        }
        if(head->val == prev)
            return head->next;
        return head;
    }
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(INT_MAX, head);
        ListNode* ptr = dummy;
        while(ptr){
            ListNode* cur = ptr->next;
            while(cur && cur->next && cur->val == cur->next->val){
                cur = cur->next;
            }
            if(cur == ptr->next) // 下一步没重复，放心走
                ptr = ptr->next;
            else // 有重复 cur必不为nullptr，否则就是没重复那步
                ptr->next = cur->next;
        }
        return dummy->next;
    }
};