【題目描述】

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving onlydistinctnumbers from the original list.

給定一個(gè)排序鏈表，刪除所有重復(fù)的元素只留下原鏈表中沒(méi)有重復(fù)的元素。

【題目鏈接】

www.lintcode.com/en/problem/remove-duplicates-from-sorted-list-ii/

【題目解析】

上題為保留重復(fù)值節(jié)點(diǎn)的一個(gè)，這題刪除全部重復(fù)節(jié)點(diǎn)，看似區(qū)別不大，但是考慮到鏈表頭不確定(可能被刪除，也可能保留)，因此若用傳統(tǒng)方式需要較多的if條件語(yǔ)句。這里介紹一個(gè)處理鏈表頭節(jié)點(diǎn)不確定的方法——引入dummy node.

ListNode *dummy = new ListNode(0);

dummy->next = head;

ListNode *node= dummy;

引入新的指針變量dummy，并將其next變量賦值為head，考慮到原來(lái)的鏈表頭節(jié)點(diǎn)可能被刪除，故應(yīng)該從dummy處開(kāi)始處理，這里復(fù)用了head變量?？紤]鏈表A->B->C，刪除B時(shí)，需要處理和考慮的是A和C，將A的next指向C。如果從空間使用效率考慮，可以使用head代替以上的node，含義一樣，node比較好理解點(diǎn)。

與上題不同的是，由于此題引入了新的節(jié)點(diǎn)dummy，不可再使用node->val == node->next->val，原因有二：

1此題需要將值相等的節(jié)點(diǎn)全部刪掉，而刪除鏈表的操作與節(jié)點(diǎn)前后兩個(gè)節(jié)點(diǎn)都有關(guān)系，故需要涉及三個(gè)鏈表節(jié)點(diǎn)。且刪除單向鏈表節(jié)點(diǎn)時(shí)不能刪除當(dāng)前節(jié)點(diǎn)，只能改變當(dāng)前節(jié)點(diǎn)的next指向的節(jié)點(diǎn)。

2在判斷val是否相等時(shí)需先確定node->next和node->next->next均不為空，否則不可對(duì)其進(jìn)行取值。

【參考答案】

www.jiuzhang.com/solutions/remove-duplicates-from-sorted-list-ii/