在做鏈表相關題的時候，常常需要針對頭節點單獨考慮，但實際上對頭節點進行處理的代碼邏輯與非頭節點的又特別地相似，此時通過在鏈表頭節點前增加虛擬頭節點，可以既使得代碼更加優美又能避免對頭節點得單獨考慮，
82. 洗掉排序鏈表中的重復元素 II
題意：洗掉排序鏈表中所有含有重復數字的節點，只保留原始鏈表中沒有出現的數字，
解題思路
以鏈表 1->1->1->2->3 為栗子，洗掉值為 1 的節點，
洗掉前：
洗掉后
在原鏈表的頭節點前增加虛擬頭節點：
定義兩個指標 pre/cur，分別指向虛擬頭節點和頭節點
當 cur 指向的節點的值等于其下一個節點的值時，右移 cur 直到其指向的節點的值與其下一個節點的值不等
此時，將 pre 指向的節點指向 cur 指向的節點的下一個節點，即 pre->next = cur->next，相當于洗掉鏈表中所有節點值為 1 的節點
繼續右移 cur，判斷是否還有其指向的節點的值與其下一個節點值相等，同時右移 pre，直至 cur 指向鏈表尾節點
Show me the Code
1 // c++ 2 ListNode* deleteDuplicates(ListNode* head) { 3 /* 創建虛擬頭節點 */ 4 ListNode* dummyHead = new ListNode(0); 5 dummyHead->next = head; 6 7 ListNode* pre = dummyHead; 8 while (pre->next != nullptr) { 9 ListNode *cur = pre->next; 10 /* 當前節點的值等于其下一節點的值，右移當前節點到其下一節點 */ 11 while (cur->next != nullptr && cur->val == cur->next->val) { 12 cur = cur->next; 13 } 14 15 /* 當前節點不是 pre 節點的下一節點，則將 pre 節點的下一節點指向當前 16 節點的下一節點，相當于洗掉當前所有含跟當前節點值相等的節點 */ 17 if (cur != pre->next) { 18 pre->next = cur->next; 19 /* 否則，pre 節點右移 */ 20 } else { 21 pre = pre->next; 22 } 23 } 24 25 /* 釋放虛擬頭節點空間，防止記憶體泄漏 */ 26 ListNode* retNode = dummyHead->next; 27 delete dummyHead; 28 return retNode; 29 }View Code
更多精彩
關注公眾號 『 TanLiuYi00 』，回復【演算法】或【python】即可獲取高清無碼的經典演算法或 python 電子書~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/270735.html
標籤：其他
上一篇：史上最清晰的三路快速排序