【3.25】LeetCode每日一题· 删除排序链表中的重复元素 II

2021年03月25日 9时16分

标签： LeetCode 链表

## 题目描述
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

#### 示例1
```
输入: 1->2->3->3->4->4->5
输出: 1->2->5
```

#### 示例2
```
输入: 1->1->1->2->3
输出: 2->3
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/ "题目链接")

## 解题思路
由于链表已排序，因此相同元素一定相邻，可以考虑维护三个指针`pre`、`curr`和`end`。
* `curr`表示当前节点；
* `pre`始终指向当前节点的前一个节点。对于头节点的前一个节点，可以设置一个“虚拟头节点”`h`，将其连在`head`上，这样对于链表中任何一个节点，都存在当前结点的前一个节点；
* `end`指向包含相同元素区间的最后一个元素；

如果区间包含相同元素（即包含相同元素区间长度大于1），即`curr != end`时，就将`pre`的下一个节点指向`end`的下一个节点，并将`curr`更新为`end`的下一个节点，`pre`保持不变，如下图所示。

![](https://pic.stackoverflow.wiki/uploadImages/122/192/15/106/2021/03/25/09/12/6b3d9b0a-8535-42b9-813e-975e201ca0aa.svg)
如果区间不包含相同元素（即包含相同元素区间长度为1），即`curr == end`时，此时继续扫描下一个位置，将`pre`更新为`pre->next`，`curr`更新为`currr->next`，如下图所示。

![](https://pic.stackoverflow.wiki/uploadImages/122/192/15/106/2021/03/25/09/13/e0fd986b-bb87-406e-99e2-d74f0cb5702a.svg)

### 代码
```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* h = new ListNode(0);
        h->next = head;
        ListNode* pre = h, *curr = pre->next, *end = nullptr;
        while(curr){
            end = curr;
            while(end->next && end->next->val == curr->val){
                end = end->next;
            }
            if(end != curr){
                pre->next = end->next;
                // pre = pre;
                curr = end->next;
            }else{
                pre = pre->next;
                curr = curr->next;
            }
        }
        return h->next;
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了84.65%的用户
> 内存消耗：10.9 MB，在所有 C++提交中击败了31.91%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.25】LeetCode每日一题· 删除排序链表中的重复元素 II

所有评论

暂无评论

新增评论