乐趣区

删除单链表中的重复节点

1. 删除重复节点,只保留一个
示例:
Input: 1->1->2
Output: 1->2
代码:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *pre = head, *cur = head;
while (cur) {
if (pre->val != cur->val) {
pre->next = cur;
pre = pre->next;
}
cur = cur->next;
}
if (pre) pre->next = nullptr;
return head;
}
2. 删除全部重复节点
示例:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
代码:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy, *cur = head;
while (cur) {
while (cur->next && cur->next->val == cur->val)
cur = cur->next;
if (pre->next == cur)
pre = cur;
else
pre->next = cur->next;
cur = cur->next;
}
return dummy->next; // 不能直接返回 head,因为 head 有可能被删除
}

退出移动版