[数据结构与算法]【JZ76 删除链表中重复的结点】

描述

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

数据范围： 链表长度满足 0 ≤ n≤ 1000 ，链表中的值满足 1 ≤ val ≤ 1000

进阶： 空间复杂度 O(n) ，时间复杂度 O(n)

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1

输入：{1,2,3,3,4,4,5}

返回值：{1,2,5}

示例2

输入：{1,1,1,8}

返回值：{8}

方法一：哈希表

具体做法：

1. 可以遍历一次链表用哈希表记录每个结点值出现的次数，然后在链表前加一个结点值为0的表头（返回的时候，直接返回dummy->next，加表头是为了防止删除时全部结点删完了）。
2. 再次遍历该链表，对于每个结点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。

复杂度分析：
时间复杂度：O(n)，其中n为链表结点数，一共两次遍历，unordered_map每次计数、每次查询都是O(1)
空间复杂度：O(n)，最坏情况下n个结点都不相同，哈希表长度为n

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
       if(pHead == nullptr) return nullptr; // 空链表
        unordered_map<int,int> mp;
        ListNode* pre = pHead;
        while(pre != nullptr){ //遍历链表统计每个节点值出现的次数
            mp[pre->val]++;
            pre = pre->next;
        }
        ListNode tmp = ListNode(-1);    //定义一个哑节点
        tmp.next = pHead;               //在链表前加一个表头
        pre = &tmp;
        while(pre->next != nullptr){		//再次循环链表
            if(mp[pre->next->val] != 1){  	//判断节点值计数是否为1  
                pre->next = pre->next->next; //用跳过的方式达到删除的效果
            }
            else{
                pre = pre->next;
            }
        }
        return tmp.next;//去掉表头
    }
};

运行时间：3ms
超过35.11% 用C++提交的代码
占用内存：540KB
超过24.49%用C++提交的代码

方法二：直接比较删除

具体做法：

1. 其实在遍历链表的时候也可以直接删除，因为这是一个升序链表，重复的结点都连在一起。
2. 同样给链表前加上表头，然后遍历，如果遇到了两个相邻结点相同，则新开内循环将这一段所有的相同都遍历过去，第一个相同前的结点直接连上第一个不相同值的结点。
3. 返回时依然要去掉表头。

复杂度分析：
时间复杂度：O(n)，其中n为链表结点数，只有一次遍历
空间复杂度：O(1)，只开辟了临时指针，没有额外空间

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == nullptr) return nullptr; //判空
        ListNode tmp = ListNode(-1);//哑节点
        tmp.next = pHead;//在链表前加一个表头
        ListNode* pre = &tmp;
        while(pre->next != nullptr && pre->next->next != nullptr){
            if(pre->next->val == pre->next->next->val){//遇到相邻两个结点值相同
                int value = pre->next->val;
                while(pre->next != nullptr && pre->next->val == value){//将所有相同的都跳过
                    pre->next = pre->next->next;
                }
            }
            else{
                    pre = pre->next;
            }  
        }
         return tmp.next;//返回时去掉表头
    }
};

运行时间：7ms
超过1.06% 用C++提交的代码
占用内存：532KB
超过25.72%用C++提交的代码

方法三：递归删除

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (pHead==NULL)
            return NULL;
        if (pHead!=NULL && pHead->next==NULL)
            return pHead;
        
        ListNode* current;

        if (pHead->next->val==pHead->val){
            current=pHead->next->next;
            while (current != NULL && current->val==pHead->val)
                current=current->next;
            return deleteDuplication(current);
        }
 
        else {
            current=pHead->next;
            pHead->next=deleteDuplication(current);
            return pHead;
        }   
    }
};

运行时间：4ms
超过9.71% 用C++提交的代码
占用内存：588KB
超过16.81%用C++提交的代码