82. Remove Duplicates from Sorted List II【Medium】
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.
解法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
} ListNode * dummy = new ListNode(INT_MIN);
dummy->next = head;
head = dummy;
int duplicate; while (head->next != NULL && head->next->next != NULL) {
if (head->next->val == head->next->next->val) {
duplicate = head->next->val;
while (head->next != NULL && head->next->val == duplicate) {
ListNode * temp = head->next;
free(temp);
head->next = head->next->next;
}
}
else {
head = head->next;
}
}
return dummy->next; }
};
nc
解法二：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode dummy();
dummy.next = head;
ListNode *pre = &dummy;
ListNode *cur = head;
while(cur && cur->next){
while(cur->next && cur->val == cur->next->val) cur = cur->next;
if(pre->next == cur){
pre = cur;
cur = cur->next;
} else {
cur = cur->next;
pre->next = cur;
}
}
return dummy.next;
}
};
参考了@liismn 的代码
解法三：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int flag = true; // should the current head be added ?
while(head){
while(head&&head->next&&head->val==head->next->val)
{
flag = false; // finds duplicate, set it to false
head = head->next;
}
if(flag) // if should be added
{
tail->next = head;
tail = tail->next;
}
head = head->next;
flag = true; // time for a new head value, set flag back to true
}
tail->next = nullptr; // Don't forget this... I did..
return dummy->next;
}
};
参考了@GoGoDong 的代码
解法四：
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
递归，参考了@totalheap 的代码，还不太明白