/*

题目：

	删除链表中重复的节点

*/

/*

思路：

	1、声明一个头节点head，即使首元节点被删除，也可返回head->next

	2、声明两个指针，

		一个指针qNode指向确定不会删除的链表的最后一个节点，

		一个指针pNode指向遍历的节点。

	3、记录前一个节点的preVal，直到找到与preVal不同的节点，删除中间节点。

	4、声明一个flag，指示当前节点之前的节点是否为重复节点。

*/

#include<iostream>

#include<string.h>

#include<algorithm>

#include<cmath>

#include<stdio.h>

using namespace std;

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) :

        val(x), next(NULL) {

    }

};

ListNode* deleteDuplication(ListNode* pHead)

{

    //当链表长度为0或1时

    if(!pHead || !(pHead->next)) return pHead;

    //声明头节点，统一操作

    ListNode* head = new ListNode(0);

    head->next = pHead;

    int preVal = pHead->val;

    ListNode* qNode = head;//已确认的节点

    ListNode* pNode = pHead->next;//工作节点

    bool flag = false;

    while(pNode){

        if(pNode->val != preVal){

            if(flag){

                ListNode* deleteNode = qNode->next;

                ListNode* temp = nullptr;

                while(deleteNode != pNode){

                    temp = deleteNode->next;

                    delete deleteNode;

                    deleteNode = temp;

                }

                flag = false;

                qNode->next = pNode;

            }else{

                while(qNode->next != pNode){

                    qNode = qNode->next;

                }

            }

            preVal = pNode->val;

        }else{

            flag = true;

        }

        pNode = pNode->next;

    }

    if(flag){

        ListNode* toBeDelete = qNode->next;

        qNode->next = nullptr;

        ListNode* temp = nullptr;

        while(toBeDelete){

            temp = toBeDelete->next;

            delete toBeDelete;

            toBeDelete = temp;

        }

    }

    return head->next;

}

int main(){

    ListNode* node1 = new ListNode(2);

    ListNode* node2 = new ListNode(1);

    ListNode* node3 = new ListNode(1);

    node1->next = node2;

    node2->next = node3;

    ListNode* head = deleteDuplication(node1);

    while(head){

        cout<<head->val<<" ";

        head = head->next;

    }

}