O(n)时间复杂度实现链表重复节点删除问题
技巧:伪头结点、两层循环、判断是否找到了重复节点
class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { // 1 2 3 3 4 4 5 ListNode *yummyhead = new ListNode(-1); yummyhead->next = pHead; ListNode *pre = yummyhead; ListNode *post; while (pHead) { post = pHead->next; // post要放在这里赋值,而不能放在循环体末尾赋值,是因为pHead可能为空 // 寻找不重复的结点 while (post && pHead->val == post->val) { post = post->next; } // 找到下一个不重复结点 // 需要判断是否找到了重复结点,这里明显是没找到啊 if (pHead->next == post) { pre = pHead; } else { pre->next = post; } pHead = post; } return yummyhead->next; } };