/*
 * dummy
 * 遍历所有节点t
 * p = t->next, q = p->next, q开始往下走，直到值与p不同
 * 如果p = q, t变为p
 * 如果p != q, 删除[p, q]节点
 */
#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node(int x = -1): val(x), next(nullptr) {}
};

Node* deleteRepeatedNode(Node* head){
    // 为了避免边界问题，在链表前边接一个空节点
    Node* dummy = new Node;
    dummy->next = head;
    Node* h = dummy;

    // 遍历所有结点
    while(h->next){
        Node* p = h->next; // 下一个节点
        Node* q = p->next; // 下下个节点
        // 遍历从q开始所有与p值相同的节点
        while(q && q->val == p->val) q = q->next;

        // 不存在重复节点
        if(p->next == q) h = p;
        // 存在重复节点
        else h->next = q;
    }
    return dummy->next;
}

int main(){

    // 构建链表
    vector<int> nums{1,1,1,2,3};
    Node* dummy = new Node;
    Node* p = dummy;
    for(int x : nums){
        p->next = new Node(x);
        p = p->next;
    }
    Node* head = dummy->next;
    delete dummy;


    Node* res = deleteRepeatedNode(head);
//    Node* res = head;

    // 打印
    p = res;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }
    cout<<endl;

    return 0;
}