力扣-82. 删除排序链表中的重复元素

news/2024/10/14 4:27:12

1.题目

题目地址(82. 删除排序链表中的重复元素 II - 力扣（LeetCode）)

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

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

2.题解

2.1 一次遍历

思路

1.首先注意是否需要处理空链表情况？这里 *cur = head, cur != nullptr 即可以避免空链表的情况
2.是否需要虚拟头结点？是，因为可能出现需要删除链表头部元素的可能
3.需要几个节点？首先要一个prev保存上一个非重复元素位置；其次我们需要一个cur用来表示当前位置，可能还需要一个临时节点tempy用于更新链表（便于删除）
4.对于出现重复值和没有出现重复值的处理是不一样的，我们需要进行不同的处理：
4.1对于没有出现重复值的话，我们直接将prev和cur都往后移动即可
4.2对于出现重复值的情况，我们保持prev不动，向后移动cur（同时删除当前cur节点）直到:

1.cur的值和下一个值不同为止；
2.没有下一个值了 cur->next == nullptr;
到这时，我们发现会剩下最后一个重复节点有删除，进行单独处理，同时更新prev的值

终止条件

1.删节点删的 cur == nullptr，比如像[1,2,5,5,5], 最后的几个节点均是重复节点，删除之后 cur == nullptr
2.前一步是正常后移， prev = cur, cur = cur->next; 但是没有下一个值了，不存在重复节点的问题，直接结束

代码

语言支持：C++
C++ Code:

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dummyHead = new ListNode(0, head);ListNode *prev = dummyHead, *cur = head;// 首先保证cur != nullptr, 才可能有cur->next, 不然会报错访问空指针while (cur != nullptr && cur->next != nullptr) {if (cur->val == cur->next->val) {// 处理重复节点（后面一个指针不为nullptr,才有可能存在重复节点问题）while (cur->next != nullptr && cur->val == cur->next->val) {ListNode* temp = cur;cur = cur->next;delete temp;}// 处理最后一个重复节点ListNode* temp = cur;cur = cur->next;prev->next = cur; // 更新prev->nextdelete temp;} else {prev = cur;cur = cur->next;}}return dummyHead->next;}
};