LK83-删除排序链表中的重复元素

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

遍历链表就行

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr){
            return nullptr;
        }
        ListNode*cur=head;
        while(cur->next!=nullptr){
            if(cur->val==cur->next->val){
                cur->next=cur->next->next;
            }
            else{
                cur=cur->next;
            }
        }
        return head;
    }
};

时间复杂度O(N) -n是链表长度

空间复杂度O(1) -没有开辟新空间，在原链表上移除重复节点

 

 

LK82-删除排序链表中的重复元素 II

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

遍历链表

定义三个指针n1 n2 n3

使用n2 n3去找链表中的重复区间

找到后删除n2到n3的重复区间

然后让n1链接到重复区间后面一段

继续向后遍历

边界条件控制-考虑特殊情况

11123

12333

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr){
            return nullptr;
        }
        ListNode*n1,*n2,*n3;
        n1=nullptr;
        n2=head;
        n3=head->next;
        while(n3!=nullptr){
            if(n2->val==n3->val){
                //使用n2 n3去找重复区间[n2,n3)
                while(n3!=nullptr&&n3->val==n2->val){
                    n3=n3->next;
                }
                //删除重复区间
                while(n2!=n3){
                    ListNode*next=n2->next;
                    delete n2;
                    n2=next;
                }
                //把n1链接到重复区间后面一段
                if(n1!=nullptr){
                    n1->next=n2;
                }
                else{
                    head=n2;
                }
                //迭代
                if(n3!=nullptr){
                    n3=n3->next;
                }
            }
            else{
                n1=n2;
                n2=n3;
                n3=n3->next;
            }  
        }
        return head;
    }
};

时间复杂度O(N)

空间复杂度O(1)