Linked List - Remove Duplicates from Sorted List
优质
小牛编辑
124浏览
2023-12-01
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
这题要求在一个有序的链表里面删除重复的元素,只保留一个,也是比较简单的一个题目,我们只需要判断当前指针以及下一个指针时候重复,如果是,则删除下一个指针就可以了。
代码如下:
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(!head) {
return head;
}
int val = head->val;
ListNode* p = head;
while(p && p->next) {
if(p->next->val != val) {
val = p->next->val;
p = p->next;
} else {
//删除next
ListNode* n = p->next->next;
p->next = n;
}
}
return head;
}
};
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
这题需要在一个有序的链表里面删除所有的重复元素的节点。因为不同于上题可以保留一个,这次需要全部删除,所以我们遍历的时候需要记录一个prev节点,用来处理删除节点之后节点重新连接的问题。
代码如下:
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(!head) {
return head;
}
//用一个dummy节点来当做head的prev
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
ListNode* p = head;
while(p && p->next) {
//如果没有重复,则prev为p,next为p->next
if(p->val != p->next->val) {
prev = p;
p = p->next;
} else {
//如果有重复,则继续遍历,直到不重复的节点
int val = p->val;
ListNode* n = p->next->next;
while(n) {
if(n->val != val) {
break;
}
n = n->next;
}
//删除重复节点
prev->next = n;
p = n;
}
}
return dummy.next;
}
};