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;
}
};
优化代码
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);
}
}
};
总结
一开始自己写的循规蹈矩,同时移动三个指针,效率上很低,很憨憨,稍微改进了一下好很多。递归代码参考:https://www.cnblogs.com/AndyJee/p/4467051.html
网友评论