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

2021年03月26日 11时23分

标签： LeetCode 链表

## 题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素**只出现一次**。

返回同样按升序排列的结果链表。

#### 示例1
![](https://assets.leetcode.com/uploads/2021/01/04/list1.jpg)
```
输入：head = [1,1,2]
输出：[1,2]
```

#### 示例2
![](https://assets.leetcode.com/uploads/2021/01/04/list2.jpg)
```
输入：head = [1,1,2,3,3]
输出：[1,2,3]
```

#### 提示
```
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
```

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

## 解题思路
和昨天的每日一题[删除排序链表中的重复元素II](http://www.vison307.com/46/)思路类似，只是昨天的题目中，如果某一元素是重复的，则链表中出现的钙元素都要被删除，而今天的题目要求保留重复元素中的一个元素。

我们依然维护`curr`和`end`指针，表示链表中重复元素的区间。由于需要保留一个元素，因此不必再记录`curr`指针的前一个指针`pre`。
1. 将`curr`指针指向链表头节点，`end`指针和`curr`指针指向相同位置；
2. 往后遍历`end`指针，直到`end`指向的下一个位置的值和`curr`指针指向的值不同为止（亦即，`end`指针指向了当前区间的最后一个重复元素）；
3. 将`curr`指针的下一个元素置为`end`指针的下一个元素；
4. 更新`curr`指向下一个元素，`end`和`curr`指向相同位置。重复2-3。

### 代码
```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 *curr = head, *end = head;
        while(curr){
            while(end->next && end->next->val == curr->val){
                end = end->next;
            }
            if(end != curr){
                curr->next = end->next;
            }
            curr = curr->next;
            end = curr;
        }
        return head;
    }
};
```

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

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

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

所有评论

暂无评论

新增评论