题解 | #删除链表中重复的结点#

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;
    }
};