Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
AC代碼
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !(head->next)) return head;
ListNode *nope = new ListNode(-1), *ret = nope;
nope->next = head;
ListNode* pre = head;
head = head->next;
while (head) {
if (pre->val != head->val) {
head = head->next;
pre = pre->next;
nope = nope->next;
}
else {
while (head->next && head->next->val == head->val) {
head = head->next;
pre = pre->next;
}
nope->next = head->next;
if (head->next && head->next->next) {
pre = head->next;
head = head->next->next;
}
else break;
}
}
return ret->next;
}
};
優(yōu)化代碼
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *pre = new ListNode(-1), *ret = pre;
pre->next = head;
while (pre->next) {
head = pre->next;
while (head->next && head->next->val == head->val)
head = head->next;
if (head == pre->next)
pre = pre->next;
else
pre->next = head->next;
}
return ret->next;
}
};
遞歸代碼
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !(head->next)) return head;
ListNode* p = head->next;
if (p->val != head->val) {
head->next = deleteDuplicates(p);
return head;
}
else {
while (p && p->val == head->val) p = p->next;
return deleteDuplicates(p);
}
}
};
總結(jié)
一開始自己寫的循規(guī)蹈矩璧函，同時(shí)移動(dòng)三個(gè)指針亚隅，效率上很低仅颇，很憨憨冯挎，稍微改進(jìn)了一下好很多摊灭。遞歸代碼參考：https://www.cnblogs.com/AndyJee/p/4467051.html
