LeetCode 0082 - Remove Duplicates from Sorted List II
# Hints
- 链表 + 水题
# 前置题目
LeetCode 0083 - Remove Duplicates from Sorted List
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
# 题意
给定一个有序链表,要求去除其中出现重复的所有元素,仅保留在原链表中无重复的元素。
# 题解
水题,按题意模拟即可。
# AC代码
/**
* 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) {
// 特判
if (head == nullptr) {
return head;
}
// 初始化
ListNode * phead = new ListNode(0, head);
// 求解
ListNode * prv = phead;
while (prv != nullptr && prv->next != nullptr) {
ListNode * p = prv->next;
if (p->next != nullptr && p->val == p->next->val) {
// 去重
do {
ListNode * q = p;
p = p->next;
delete q;
} while (p->next != nullptr && p->val == p->next->val);
prv->next = p->next;
} else {
// 递进
prv = prv->next;
}
// 递进
}
// 返回
return phead->next;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01