删除单链表中值重复出现的节点

一、题目

这种题目包括：无序的单链表和有序的单链表

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

leetcode：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

二、思路

对于无序的单链表。

我们可以使用哈希表存储单链表中每一个元素，如果发现存在相同的元素，那就直接删除就好。
我们也可以使用选择排序的方法。首先拿到第一个元素，遍历剩下的所有元素，删除和第一个元素相等的节点。再拿到第二个元素，遍历剩下的元素；依次类推，知道遍历到最后一个元素后终止。

对于有序的单链表

就比较简单，我们可以边遍历，边删除。相同的节点总是出现在一起。

三、code

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 头节点肯定不会被删除
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* cur = head, *next = nullptr;
        for (; cur != nullptr && cur->next != nullptr;) {
            next = cur->next;
            if (cur->val == next->val) {
                cur->next = next->next;
                delete next;
                continue;
            }
            cur = cur->next;
        }
        return head;
    }
};

对于无序的单链表，思路有了，代码其实也就那样，信手拈来即可。