剑指56-删除链表中重复的结点

😔

关于链表的题我还存在有阴影，因为之前手写逆转链表写不出来，这次的题看起来很简单，但实际写起来还是有问题，着实打击自信，不过后来在我生硬的20多次提交之后，终于通过了！

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

在解这个题之前，有必要说明一下，这里重复的数字都是相邻的，题目没说，不够默认时相邻的

解法

这个题的解法其实写出来就一两句话：

1. 定义一个新的链表
2. 使用两个相邻的指针
3. 这两个指针值相等，就把前一个指针的结点添加到新链表，不相等就向前走，直到不想等

其实就是上面的三个步骤，但是有几个需要注意的地方

1. 原链表为空直接返回

2. 在判断重复之后，不管是否重复，都要前进一步。这是为了避免添加到重复的最后一个元素，例如

   

   红色是前进到不重复的元素，绿色是多前进一步，否则添加红色current将会出错

   当重复时，前进一步是为了避免添加最后一个重复的元素；不重复时，前进一步是为了添判断下一个元素

3. 最后循环结束再添加最后一个current，因为nxt到null就退出，此时的current还未添加

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode *newHead=new ListNode(0);
        ListNode *res=newHead;

        ListNode *current=pHead;
        if(!current) return res->next;
        ListNode *nxt=pHead->next;
        //if(!nxt) return current;

        while(nxt)
        {
            if(current->val==nxt->val){
                while(nxt && current->val==nxt->val) //如果相同就一直往前走
                {
                    current=nxt;
                    nxt=nxt->next;
                }
            }
            else //否则就添加到新链表
            {
                newHead->next=current;
                newHead=newHead->next;
            }

            //不管是否重复，都要前进一步，当重复时，前进一步是为了避免添加最后一个重复的元素；不重复时，前进一步是为了添判断下一个元素
            current=current->next;
            if(nxt) nxt=nxt->next;
        }
        //由于上面的重复时多前进一部，会导致nxt可能为null直接退出，所以最后得把current元素加上
        newHead->next=current;
        newHead=newHead->next;
        return res->next;
    }
};