//删除排序链表中重复的节点 //注意如果头结点是重复的，那么删除节点之后防止链表散掉

  #include <iostream>
    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    //构建链表，显示链表
    struct ListNode
    {
        int       m_nValue;
        ListNode* m_pNext;
    };

    ListNode* CreateListNode(int value);
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);
    void PrintListNode(ListNode* pNode);
    void PrintList(ListNode* pHead);
    void DestroyList(ListNode* pHead);
    void AddToTail(ListNode** pHead, int value);

    ListNode* CreateListNode(int value)
    {
        ListNode* pNode = new ListNode();
        pNode->m_nValue = value;
        pNode->m_pNext = NULL;

        return pNode;
    }

    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
    {
        if(pCurrent == NULL)
        {
            printf("Error to connect two nodes.\n");
            exit(1);
        }

        pCurrent->m_pNext = pNext;
    }

    void PrintListNode(ListNode* pNode)
    {
        if(pNode == NULL)
        {
            printf("The node is NULL\n");
        }
        else
        {
            printf("The key in node is %d.\n", pNode->m_nValue);
        }
    }

    void PrintList(ListNode* pHead)
    {
        printf("PrintList starts.\n");

        ListNode* pNode = pHead;
        while(pNode != NULL)
        {
            printf("%d\t", pNode->m_nValue);
            pNode = pNode->m_pNext;
        }

        printf("\nPrintList ends.\n");
    }

    void DestroyList(ListNode* pHead)
    {
        ListNode* pNode = pHead;
        while(pNode != NULL)
        {
            pHead = pHead->m_pNext;
            delete pNode;
            pNode = pHead;
        }
    }

    void AddToTail(ListNode** pHead, int value)
    {
        ListNode* pNew = new ListNode();
        pNew->m_nValue = value;
        pNew->m_pNext = NULL;

        if(*pHead == NULL)
        {
            *pHead = pNew;
        }
        else
        {
            ListNode* pNode = *pHead;
            while(pNode->m_pNext != NULL)
                pNode = pNode->m_pNext;

            pNode->m_pNext = pNew;
        }
    }
//删除重复节点
void deleteDuplication(ListNode** pHead){//头结点也有可能被删除**
    if(pHead==NULL || *pHead==NULL)
        return;
    ListNode* pPreNode=NULL;
    ListNode* pNode=*pHead;
    while(pNode!=NULL){
        ListNode* pNext=pNode->m_pNext;
        bool needDeleted=false;

        if(pNext!=NULL && pNext->m_nValue==pNode->m_nValue)//重复
            needDeleted=true;

        if(!needDeleted){
            pPreNode=pNode;
            pNode=pNode->m_pNext;//继续往后找有没有重复的
        }
        else{
            int value=pNode->m_nValue;
            ListNode* pToBeDel=pNode;

            while(pToBeDel!=NULL && pToBeDel->m_nValue==value){
                pNext=pToBeDel->m_pNext;

                delete pToBeDel;
                pToBeDel=NULL;

                pToBeDel=pNext;
            }
            if(pPreNode==NULL)//头结点重复了
                *pHead=pNext;
            else
                pPreNode->m_pNext=pNext;
            pNode=pNext;//继续下一个判断
        }
    }

}
int main()
{
//构建链表

    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(3);
    ListNode* pNode5 = CreateListNode(5);
    ListNode* pNode6 = CreateListNode(6);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
    ConnectListNodes(pNode5, pNode6);

    ListNode* pHead=pNode1;
    deleteDuplication(&pHead);
    PrintList(pHead);
    return 0;
}