描述
在一個(gè)排序單鏈表中伟姐，刪除節(jié)點(diǎn)值重復(fù)出現(xiàn)的節(jié)點(diǎn)查吊，保證每個(gè)節(jié)點(diǎn)的值只出現(xiàn)一次通惫。
分析
單鏈表中可以訪問(wèn)到當(dāng)前節(jié)點(diǎn)(curNode)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（nextNode）鼻忠，根據(jù)題意需要判斷當(dāng)前節(jié)點(diǎn)值和下一個(gè)節(jié)點(diǎn)值的兩種關(guān)系：
1，不相等凳兵，當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)百新，下一個(gè)節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)；
2庐扫，相等饭望，當(dāng)前節(jié)點(diǎn)的next指針指向nextNode->next，將下一個(gè)節(jié)點(diǎn)從鏈表中拆除聚蝶；更改下一個(gè)節(jié)點(diǎn)的指向杰妓，繼續(xù)判斷；
實(shí)現(xiàn)
迭代版碘勉，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
ListNode *removeDuplicatesFromSortedList(ListNode *head)
{
ListNode *pCur = head;
while (pCur->next) {
ListNode *pNext = pCur->next;
if (pNext->val == pCur->val) {
//處理相等的元素
pCur->next = pNext->next;
delete pNext;
continue;
}
// 處理不相等的情況
pCur = pNext;
}
return head;
}
遞歸版桩卵，時(shí)間復(fù)雜度O(n)验靡，空間復(fù)雜度O(1)
ListNode *removeDuplicatesFromSortedListUseRecursion(ListNode *head)
{
if (!head->next) {
return head;
}
ListNode *next = head->next;
// 不相等
if (next->val != head->val) {
return removeDuplicatesFromSortedListUseRecursion(head->next);
}
// 相等
head->next = next->next;
delete next;
return removeDuplicatesFromSortedListUseRecursion(head);
}
