在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。
时间: 2024-06-06 12:11:11 浏览: 11
例如,链表1->2->3->3->4->4->5 处理后为 1->2->5。
算法1:双指针
思路:
- 定义一个前节点和当前节点
- 当前节点和后面的节点比较,如果相等,就删除后面的节点,如果不相等,前节点和当前节点同时向后移动
时间复杂度:O(n)
空间复杂度:O(1)
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
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;
}
pre->next = cur->next;
} else {
pre = pre->next;
}
cur = cur->next;
}
return dummy->next;
}
};
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)