描述

这是一篇针对初学者的题解，使用两种方法解决。
知识点：单链表
难度：一星

题解

题目抽象：给定一个单链表，删除单链表中重复的值。

方法一：使用set，暴力解法

根据题意，显然如果能够知道重复的值是什么，然后再遍历一次单链表，删除重复值即可。
找重复值的具体步骤：
1.初始化：set<int> st
2. 遍历单链表相邻两个元素，如果相等，就加入到set当中
3. 直到单链表遍历完

删除重复值的具体步骤：
1.初始化：pre指针指向重复值的前一个节点，cur指向当前遍历的节点值
2.遍历单链表当前元素，然后再set中检查，如果是重复值，就删除，pre->next = cur->next
3. 否则，不是重复值，pre = pre->next, cur = cur->next
4. 知道单链表遍历完

代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (!pHead) return pHead;
        set<int> st;
        ListNode *pre = pHead;
        ListNode *cur = pHead->next;
        while (cur) {
            if (pre->val == cur->val) {
                st.insert(pre->val);
            }
            pre = pre->next;
            cur = cur->next;
        }

        ListNode *vhead = new ListNode(-1);
        vhead->next = pHead;
        pre = vhead;
        cur = pHead;
        while (cur) {
            if (st.count(cur->val)) {
                cur = cur->next;
                pre->next = cur;     
            }
            else {
                pre = pre->next;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};

时间复杂度：O(2n),遍历了2次单链表
空间复杂度：最坏O(n), 最好O(1)

方法二：直接删除法

根据方法一，可以优化，在遍历单链表的时候，检查当前节点与下一点是否为相同值，如果相同，继续查找祥同值的最大长度，然后指针改变指向。

代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode *vhead = new ListNode(-1);
        vhead->next = pHead;
        ListNode *pre = vhead, *cur = pHead;        
        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
                while (cur->next && cur->val == cur->next->val) {
                    cur = cur->next;
                }
                cur = cur->next;
                pre->next = cur;
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)