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

比较容易想到，但不容易写对:)

我的思路是，既然对链表做了修改，就索性新建一个，把符合条件的节点拷贝出来。所以问题就成了怎么找到符合条件的节点？

很明显，需要用到至少两个指针，用来判断相邻两个节点的值是否相等。然后设置一个标志位，保存上次判断相邻两个节点值相等的状态，然后向下遍历，每次不断更新和判断这个标志位，如果满足题目要求就拷贝出来。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(!pHead) return pHead;
        ListNode* pNewHead = nullptr;
        bool same = false;
        ListNode* pCur = pHead;
        ListNode* pNext = pHead->next;
        while(1){
            if(!pNext){
                if(!same){
                    pNewHead = add2New(pNewHead, pCur);
                }
                break;
            }
            if(pCur->val == pNext->val){
                same = true;
            }
            else{
                if(same){
                    same = false;
                }
                else{
                    pNewHead = add2New(pNewHead, pCur);
                }
            }
            pCur = pNext;
            pNext = pNext->next;
        }
        return pNewHead;
    }
    
    ListNode* add2New(ListNode* pNewHead, ListNode* newNode){
        if(!pNewHead){
            pNewHead = new ListNode(newNode->val);
            pNewHead->next = nullptr;
        }
        else{
            ListNode* added = new ListNode(newNode->val);
            added->next = nullptr;
            ListNode* pTail = pNewHead;
            while(pTail->next){
                pTail = pTail->next;
            }
            pTail->next = added;
        }
        return pNewHead;
    }
};