剑指offer：删除链表中重复的节点

原题链接：https://www.acwing.com/problem/content/27/

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* deleteDuplication(ListNode* head) {
    
        // 创建虚拟头节点，方便后边的删除操作
        auto dummy = new ListNode(-1);
        dummy->next = head;
        
        // 分成三段来看待。已经处理过的，
        // 要处理的，还有下下段。
        
        auto p = dummy;
        // p存放已经处理过的一段的末尾节点
        while(p->next)
        {
    
            // q指向下一段的开始
            auto q = p->next;
            // 下一段不空，并且下一段相等，q就一直往
            // 后走，最后q指向下下段。
            while(q && p->next->val == q->val)
                q = q->next;
            
            // 如果这段长度为1。p直接往后走
            if(p->next->next == q) p = p->next;
            // 不为1，则删除，p->next直接指向下下段的开头
            else p->next = q;
        }
        
        return dummy->next;
    }
};```