描述

题目描述

首先给我们一个链表，是已经排好顺序的链表，我们要做的事情就是把重复的元素全部删除掉就可以了，最后返回我们删除过后的链表

样例解释

首先给定我们的输入

{1,1,1,5}

这里我们可以得到这么一个链表，如图所示

然后我们发现我们权值为$11$的点重复出现了$33$次，然后我们删掉，最后得到的一个链表就是

最后我们的输出就是

{5}

然后一般对于这种链表的解题思想无非就是分为两种，一种是递归，一种是迭代

题解

解法一：迭代法

解题思路：

我们可以一开始先定义一个哑节点，然后我们在进行操作的时候，我们可以每次从我们的哑节点的后面开始找，最多会有多少个一样的，然后我们把这些一样的节点全部删掉，如果没有一样的我们可以正常移动我们的指针，最后返回我们的哑节点的后一个节点，就是我们原来头节点的位置

图解代码：

代码实现：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode* dummy = new ListNode(0);
        dummy->next = pHead;
//         定义一个哑节点在我们原来的头节点的前面
        ListNode* cur = dummy;
//         定义一个新的用于中间判断的节点
        while (cur->next && cur->next->next) {
//             当我们这个节点的后两个节点不为空的时候
            if (cur->next->val == cur->next->next->val) {
//                 如果他们的值相同
                int val = cur->next->val;
//                 记录这个值
                while (cur->next && cur->next->val == val) 
                    cur->next = cur->next->next;
//                 一直删除到没有相同的值为止
            } else {
                cur = cur->next;
            }
//             否则就是正常的移动我们的节点
        }
        return dummy->next;
//         返回我们哑节点的后一个节点，也就是我们的原来的头节点
    }
};

时空复杂度分析：

时间复杂度： $O(n)O(n)$

理由如下：我们只是简单的遍历了一次我们的整个链表

空间复杂度： $O(1)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;
//         如果我们的头节点或者头节点的下一个节点是空的我们直接返回
        if (pHead->val != pHead->next->val) {
            pHead->next = deleteDuplication(pHead->next);
//             第一种我们两个挨着的不相等，那么我们可以前面的节点不删除，递归判断后面的节点
        } else {
//             如果两个节点相同
            ListNode* cur = pHead->next;
            while (cur && cur->val == pHead->val) 
                cur = cur->next;
//             我们找到最后一个相同的节点，然后我们返回这个节点之后递归判断的结果
            return deleteDuplication(cur);
        }
        return pHead;
//         最后返回我们的头节点
    }
};

时空复杂度分析

时间复杂度： $O(n)O(n)$

理由如下：因为我们一共只是遍历了一次我们的链表

空间复杂度： $O(n)O(n)$

理由如下：我们的递归操作会调用我们系统的栈