删除有序链表中重复的元素-II（C++）

目录

问题描述

示例1

示例2

解题思路

代码实现

代码解析

1. 初始化

2. 遍历链表

总结

问题描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→51→2→3→3→4→4→5, 返回1→2→51→2→5.
给出的链表为1→1→1→2→31→1→1→2→3, 返回2→32→3.

数据范围：链表长度 0≤n≤100000≤n≤10000，链表中的值满足 ∣val∣≤1000∣val∣≤1000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

示例1

输入：

{1,2,2}

返回值：

{1}

示例2

输入：

{}

返回值：

{}

解题思路

首先，创建一个虚拟头节点 pre，并初始化一个指针 p 用于追踪新链表的尾部，指针 cur 用于遍历原链表。然后，使用 cur 指针遍历链表，当遇到 cur 和 cur->next 节点值相等时，说明存在重复元素，继续移动 cur 指针跳过所有重复的节点，直到找到一个不同的节点。如果没有重复元素，则将当前节点 cur 加入新链表，并更新指针 p。这个过程会一直执行，直到遍历完整个链表。最后，返回虚拟头节点 pre 后的节点，构成去重后的链表。

代码实现

    ListNode* deleteDuplicates(ListNode* head) {// write code hereListNode* pre = new ListNode(-1);ListNode* p = pre;ListNode* cur = head;while(cur != nullptr){if(cur->next != nullptr && cur->val == cur->next->val){while(cur->next != nullptr && cur->val == cur->next->val){cur = cur->next;}cur = cur->next;if(cur == nullptr) p->next = nullptr;}else {p->next = cur;cur = cur->next;p = p->next;}}return pre->next;}

代码解析

1. 初始化

ListNode* pre = new ListNode(-1);
ListNode* p = pre;
ListNode* cur = head;

创建虚拟头节点，并初始化指针。p 用于构建新的链表，初始指向虚拟头节点 pre。cur 用于遍历原链表，初始指向输入链表的头节点 head。

2. 遍历链表

        while(cur != nullptr){if(cur->next != nullptr && cur->val == cur->next->val){while(cur->next != nullptr && cur->val == cur->next->val){cur = cur->next;}cur = cur->next;if(cur == nullptr) p->next = nullptr;}else {p->next = cur;cur = cur->next;p = p->next;}}

while 循环用于遍历链表，直到 cur 指向 nullptr，即遍历到链表的末尾为止。当当前节点的值与下一个节点的值相等时，说明遇到重复的元素。此时，跳过所有值相同的重复节点，直到遇到一个不同的节点，跳过重复节点后，将 cur 移动到下一个节点，继续遍历。如果当前节点没有重复（即 cur->val != cur->next->val），则将当前节点 cur 加入新的链表，更新 p 指针指向当前节点，并将 cur 移动到下一个节点。

总结

代码通过遍历排序链表，删除所有重复的节点，保留唯一的元素。使用一个虚拟头节点简化链表操作，并用两个指针 cur 和 p 分别负责遍历原链表和构建去重后的新链表。当遇到重复节点时，跳过所有重复元素，直到找到一个不同的节点，继续将其添加到新链表中。最终返回去重后的链表。