删除排序链表中的重复元素-leetcode83(循环不变式)

题目：leetcode83

解答：

官方答案

算法思想：边比较边连接

ListNode* deleteDuplicates(ListNode* head) {
        ListNode* current = head;
        while(current!=NULL && current->next!=NULL)
        {
            if(current->val == current->next->val)
            {
                current->next = current->next->next;
            }else{
                current = current->next;
            }
        }
        return head;
    }

时间复杂度：n，空间复杂度：1//用一个指针

8ms;-0.04%

自己写的答案，leetcode登录不上没提交

算法思想：先比较找出第一个不同的位置，再连接

ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return nullptr;//空指针测试用例
        ListNode* first = head;
        ListNode* last = head;
        while(last!=nullptr)
        {
            if(last->val != first->val)
            {
                first->next = last;
                first = last;
            }
            last = last->next;
        }
        first->next = nullptr;//尾指针的处理
        return head;
    }

时间复杂度：n；空间复杂度：1//两个指针

8ms;-0.04%

拓展补充：

① “循环不变式”验证算法的正确性-有点类似第一数学归纳法
Leetcode官方验证步骤
循环不变式-百度百科
② c++中NULL与nullptr的区别
c++中NULL实际上就是0，当重载整型的情况下，会把NULL当做0处理；而nullptr是c++11加入的，在任何时候都可以表示空指针
c++中NULL与nullptr的区别