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

描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 输入： {1,2,3,3,4,4,5} 复制 返回值： {1,2,5} 首先初始化一个起始指针preNode指向头结点、工作指针walkNode指向链表的第一个元素，即preNode.next=walkNode。 迭***始： while(walkNode!=null){ 　　如果当前工作结点的数据域walkNode.val与下一个结点的数据域walkNode.next.val相同（出现重复结点）： 　　　　preNode不移动；（指向重复结点段的前一个结点） 　　　　walkNode移动：walkNode=walkNode.next；（此时preNode.next!=walkNode） 　　否则， 　　　　如果preNode.next==walkNode（说明未出现重复节点）： 　　　　　　preNode移动，walkNode移动：preNode=walkNode；walkNode=walkNode.next； 　　否则，说明有重复结点，此时preNode指向重复结点段的前一个结点，walkNode指向重复结点段的最后一个重复结点 　　　　　　使preNode直接指向重复结点段的下一个结点：preNode.next=walkNode.next; 　　　　　　walkNode移动：walkNode=walkNode.next； } 注意：因为可能会删除头结点，例如{1，1，1，2}，删除了头结点1和第一个结点1，结果应为{2}。但是如果直接将函数传进来的pHead作为头结点，即初始化preNode=pHead，那么头节点永远不可能被删除，得到的结果只能为{1,2}。 因此这里添加了一个新的头节点newhead，将pHead当一般结点处理，初始化preNode=newhead这样就可以避免出现上面的错误。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==NULL)
            return NULL;
        ListNode* walkNode = pHead;
        ListNode* newhead = new ListNode(0);
        newhead->next=pHead;
        ListNode* preNode = newhead;
        while(walkNode->next != NULL){
            if(walkNode->val == walkNode->next->val)
            {
                walkNode=walkNode->next;
            }else
            {
                if(preNode->next==walkNode)
                {
                    preNode=walkNode;
                    walkNode=walkNode->next;
                }
                else{
                    preNode->next=walkNode->next;
                    walkNode=walkNode->next;
                }
            }
        }
        if(walkNode->next==NULL)
        {
            if(preNode->next != walkNode && preNode==newhead)
            {
                newhead->next=NULL;
            }else if(preNode->next != walkNode && preNode!=newhead)
            {
                preNode->next=NULL;
            }
        }
        return newhead->next;
    }
};