题解 |【清晰图解】 #删除有序链表中重复的元素-II#快进来！快进来！！

题意很简单

在一个有序链表中，如果说一个节点的值出现不止一次，那么把所有等于此值的节点全部删掉。

传统手艺，延年益寿😜

alt

别看图拉，看黑板！

因为是有序链表，那如果一个节点的值出现不止一次，那么这两个值肯定是相邻的哦。

三种解法来做

下面用两种方法：递归，迭代，其中迭代又分为两种方法。

递归来解

链表和树的问题，一般都可以用递归和迭代两种写法来解。对于这道题你一定记住它是有序链表，所以值相同的节点会在一起的，这个我前面已经说过了。

1.1 递归函数定义

递归最基本的是要明白递归函数的定义！我反复反复强调过这一点。

递归函数直接使用题目给出的函数 deleteDuplicates(head)，它的含义是删除以 head 作为开头的有序链表中，值出现重复的节点。

1.2 递归终止条件

终止条件就是能想到的基本的、不用继续递归处理的情况

如果 head 为空，那么肯定没有值出现重复的节点，所以直接返回 head；
那如果 head.next 为空，那说明链表中只有一个节点，也没有值出现重复的节点，也直接返回 head 即可。

1.3 递归调用

什么时候需要递归呢？我们想一下有两种情况：

如果 head.val != head.next.val ，说明头节点的值不等于下一个节点的值，所以当前的 head 节点必须保留下来；但是 head.next 节点要不要保留呢？我们还不知道，需要对 head.next 进行递归，即对 head.next 作为头节点的链表，去除值重复的节点。所以 head.next = self.deleteDuplicates(head.next),那

如果 head.val == head.next.val，说明头节点的值等于下一个节点的值，所以当前的 head 节点必须删除掉，并且 head 之后所有与 head.val 相等的节点也都需要删除；删除到哪个节点为止呢？需要用 move 指针一直向后遍历寻找到与 head.val 不等的节点。此时 move 之前的节点都不保留了，所以返回 deleteDuplicates(move);

1.4 返回结果

题目让我们返回删除了值重复的节点后剩余的链表，结合上面我说的两种递归调用情况。

如果 head.val != head.next.val，头结点需要保留，所以返回的是 head；
如果 head.val == head.next.val，头结点需要删除，需要返回的是deleteDuplicates(move);

我举个例

对链表 1 -> 2 -> 2 -> 3 递归的过程如下。

//c++这样来写
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        if (head->val != head->next->val) {
            head->next = deleteDuplicates(head->next);
        } else {
            ListNode* move = head->next;
            while (move && head->val == move->val) {
                move = move->next;
            }
            return deleteDuplicates(move);
        }
        return head;
    }
};

复杂度分析下

时间复杂度是O(N)，因为每个节点只访问了一次。
空间复杂度是O(N)，递归调用的时候会只用了系统的栈。

迭代来解

迭代法，我写了两种。一个是利用有序链表这个性质的，二是直接计数统计出现次数的。

1 一次遍历

这里说的一次遍历，是说一边遍历、一边来统计相邻节点的值是否相等，如果说值相等就继续后移找到值不等的位置，然后删除值相等的这个区间。

其实我上面这个思路很简单，跟递归方法中的 while 语句跳过所有值相等的节点的思路是一毛一样：

如果 cur.val == cur.next.val 说明两个相邻的节点值相等，所以继续后移，一直找到 cur.val != cur.next.val ，此时的 cur.next 就是值不等的节点了。

比方说： 1 -> 2 -> 2 -> 2 -> 3，我们用一个 pre 指向 1；当 cur 指向第一个 2 的时候，发现 cur.val == cur.next.val ，所以出现了值重复的节点啊，所以 cur 一直后移到最后一个 2 的时候，发现 cur.val != cur.next.val ，此时 cur.next = 3 ，所以 pre.next = cur.next ，即让1 的 next 节点是 3，就把中间的所有 2 都删了。

其中我们代码里面用到了一个常用的技巧：dummy 节点，也叫它哑节点。它在链表的迭代写法中非常常见，因为对于本题而言，我们可能会删除头结点 head，为了维护一个不变的头节点，所以我们添加了 dummy，让dummy.next = head，这样即使 head 被删了，那么会操作 dummy.next 指向新的链表头部，所以最终返回的也是 dummy.next。

//c++这样来写
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* preHead = new ListNode(0);
        preHead->next = head;
        ListNode* pre = preHead;
        ListNode* cur = head;
        while (cur) {
            //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
            while (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
            }
            if (pre->next == cur) {
                //pre和cur之间没有重复节点，pre后移
                pre = pre->next; 
            } else {
                //pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
                //但是pre不移动，仍然指向已经遍历的链表结尾
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return preHead->next;
    }
};

时间复杂度是O(N)，因为对链表中每个节点进行遍历了一次；
空间复杂度是O(1)，只用了常量的空间。

利用计数，进行两次遍历

这个做法是已经忽略了链表有序这个性质，使用了两次遍历，第一次遍历呢统计每个节点的值出现的次数，第二次遍历的时候额，如果发现 head.next 的 val 出现次数不是 1 次，就需要删除 head.next，所以我们得到以下的代码：

//c++这样来写
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        unordered_map<int, int> m;
        ListNode dummy(0);
        ListNode* dummy_move = &dummy;
        ListNode* move = head;
        while (move) {
            m[move->val]++;
            move = move->next;
        }
        move = head;
        while (move) {
            if (m[move->val] == 1) {
                dummy_move->next = move;
                dummy_move = dummy_move->next;
            }
            move = move->next;
        }
        dummy_move->next = nullptr;
        return dummy.next;
    }
};