給定一個排序鍊表，删除所有含有重複數字的節點，隻保留原始鍊表中沒有重複出現的數字。 示例1: 輸入: 1->2->3->3->4->4->5 輸出: 1->2->5 示例2: 輸入: 1->1->1->2->3 輸出: 2->3

// // Created by tannzh on 2020/8/19. // /* * 删除排序鍊表中的重複元素 II 給定一個排序鍊表，删除所有含有重複數字的節點，隻保留原始鍊表中沒有重複出現的數字。 示例1: 輸入: 1->2->3->3->4->4->5 輸出: 1->2->5 示例2: 輸入: 1->1->1->2->3 輸出: 2->3 */ #include <iostream> //Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == nullptr) return head; ListNode preHead(0); preHead.next = head; ListNode *pre = &preHead; bool isDuplicate = false; ListNode *p = head; while (p->next) if (p->val == p->next->val) { ListNode *next = p->next->next; delete p->next; p->next = next; isDuplicate = true; } else if (isDuplicate) { ListNode *next = p->next; delete p; p = next; pre->next = p; isDuplicate = false; } else { pre = p; p = p->next; } if (isDuplicate) { ListNode *next = p->next; delete p; pre->next = next; } return preHead.next; } }; ListNode *create_linkedlist(std::initializer_list<int> lst) { auto iter = lst.begin(); ListNode *head = lst.size() ? new ListNode(*iter ) : nullptr; for (ListNode *cur=head; iter != lst.end(); cur=cur->next) cur->next = new ListNode(*iter ); return head; } int main(int argc, char **argv) { Solution s; ListNode *head = s.deleteDuplicates(create_linkedlist({1,1,2,2,3,4})); for (ListNode *cur=head; cur; cur=cur->next) std::cout << cur->val << "->"; std::cout << "\b\b " << std::endl; return 0; }

這道題沒有太多可說的，屬于基本題的擴展。

可以先參考前面的 [12. Remove Duplicates from Sorted List](../12. Remove Duplicates from Sorted List).而這道題多出的一點把戲在于，要把重複的數據删的幹幹淨淨。我的策略很簡單，将重複的數據做一個标記，`isDuplicate`, 然後再删掉重複元素的基礎上，最後給剩下那個光棍補上一刀。雖然有點啰嗦，但是效率還過得去。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!