题目链接

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

18.2 删除链表中重复的结点II - 图1

解题思路

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

根据题意，显然如果能够知道重复的值是什么，然后再遍历一次单链表，删除重复值即可。
找重复值的具体步骤：
1.初始化：set 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)

方法二：直接删除法

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(!pHead||!pHead->next)
            return pHead;
        ListNode *vhead = new ListNode(-1);
        vhead->next = pHead;
        ListNode *pre = vhead,*cur = pHead;
        while(cur){
            if(cur->next&&(cur->val==cur->next->val)){
                int tmp = cur->val;
                while(cur&&cur->val==tmp){
                    cur = cur->next;
                }
                pre->next = cur;
            }else{
                pre = cur;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode* hair = new ListNode(0);
        hair->next = pHead;
        ListNode* pre = hair;
        ListNode* cur = pHead;
        while(cur){
            if(cur->next&&cur->val==cur->next->val){
                cur = del(cur);
                pre->next = cur;
            }else{
                pre = cur;
                cur = cur->next;
            }
        }
        return hair->next;
    }
    ListNode* del(ListNode* node){
        int val = node->val;
        while(node&&node->val==val){
            node = node->next;
        }
        return node;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode hair = new ListNode();
        hair.next = head;
        ListNode pre = hair, cur = head;
        while(cur!=null){
            int val = cur.val;
            boolean flag = true;
            while(cur.next != null && cur.next.val == val){
                cur = cur.next;
                flag = false;
            }
            if(flag){
                pre = pre.next;
            }else{
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return hair.next;
    }
}

保留重复节点中第一个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode hair = new ListNode();
        hair.next = head;
        ListNode pre = head;
        ListNode cur = head;
        while(cur!=null){
            int val = cur.val;
            while(cur!=null && cur.val == val){
                cur = cur.next;
            }
            pre.next = cur;
            pre = cur;
        }
        return hair.next;
    }
}

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