题解 | #删除有序链表中重复的元素-I#

NC25 删除有序链表中重复的元素-I

题意分析：

给一个有序的链表，删除其中的重复的元素。

题解一（遍历）：

我们初始化两个指针，指针flag指向当前编制元素，代表有其他指针的值与其相同的标志点。设置指针p，用于遍历链表。

当flag==p时候，p指向其下一个元素

当flag!=p时候，我们需要检查指针flag和指针p指向的值是否相同。如上图中间一部分，指针p和指针flag虽然指向不同的位置，但是其值相等，这是我们需要删除指针p指向的元素，我们的删除步骤如下：

1. 首先flag指针的指向的下一个元素指向p的下一个元素。
2. 删除指针p指向的元素
3. 将指针p指向flag指向的下一个元素

通过上面散步，我们删除了重复的元素

当flag!=p时候，并且他们的值不相等，我们将指针flag指向p指向的元素，之后重复上面的步骤。

当p为空的时候，说明我们已经把重复元素删除完毕，返回链表的头指针即可。

将上面步骤书写成代码：

ListNode* deleteDuplicates(ListNode* head) {
        ListNode *flag = head;
        ListNode *p = head;
        while(p){
            if(flag==p){
                 //当flag指针与遍历所用指针p重合，p移动到下一个位置，不用做删除
                p = p->next;
            }
            else if(flag!=p&&flag->val!=p->val){
                //当flag与p没有重合，且他们值不等，更新flag到p
                flag = p;
            }
            else if(flag!=p&&flag->val==p->val){
                //当flag与p没有重合，但他们的值相等，开始删除p
                flag->next = p->next;
                free(p);
                p = flag->next;
            }
        }
        return head;
    }

值得注意的是，上面删除元素的步骤也有一个错误的写法：

1. 将指针p指向p的下一个元素。
2. 将指针flag的下一个指向改为指向指针p。

这里我们并没有free 重复的元素，而是忽略了它。代码如下

 ListNode* deleteDuplicates(ListNode* head) {
        ListNode *flag = head;
        ListNode *p = head;
        while(p){
            if(flag==p){
                p = p->next;
            }
            else if(flag!=p&&flag->val!=p->val){
                flag = p;
            }
            else if(flag!=p&&flag->val==p->val){
            //与上面不同的地方
                p = p->next;
                flag->next= p;
            }
        }
        return head;
    }

这种写法虽然能够ac，但实际上并没有真正删除掉重复的元素，只是断开了重复元素在原有链表中的连接，重复元素成为了一个孤孤单单的指针，没有被回收到它该去的地方。

时间复杂度：，将链表遍历了一遍。
空间复杂度：，用到了常数个指针。