82. 删除排序链表中的重复元素 II (Leetcode刷题笔记 )

82. 删除排序链表中的重复元素 II (Leetcode刷题笔记 )

题目解题代码C++解题代码C++*****(递归)******解题代码Java*****(递归)******算法效率

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3] 输出：[2,3]

class Solution{
public:
    ListNode* deleteDuplicates(ListNode*head){
        if(!head||!head->next) return head;
        ListNode* temp0=new ListNode(0);
        //temp0相当于是一个虚的结点
        //temp1是判断过程种的一个第一个结点
        //temp2是判断过程中的末尾的结点
        temp0->next=head;
        ListNode* temp1=head;
        ListNode* res=temp0;
        ListNode* temp2=head->next;
        while(temp2){
            if(temp1->val==temp2->val){
            	//一次性遍历找到所有相同的
                while(temp1->val==temp2->val){
                    temp2=temp2->next ? temp2->next: nullptr;
                    if(!temp2){
                        break;
                    }
                }
                temp0->next=temp2?temp2:nullptr;
                temp1=temp2;
                temp2=temp2?temp2->next:nullptr;
            }else{
            	//没出现相同的，那就继续向后
                temp0=temp0->next;
                temp1=temp1->next ;
                temp2=temp2->next ;
            }
        }
        return res->next;
    }
};

class Solution{
public:
    ListNode* deleteDuplicates(ListNode*head){
        if(!head||!head->next) return head;
        ListNode*temp=head->next;

        if(head->val==temp->val){
            while(temp &&head->val==temp->val){
                temp=temp->next;
            }
           //temp开始的链做一次删除重复结点的操作
            head=deleteDuplicates(temp);
        }else{
        	//如果没有相同的，那么对head->next做一次删除重复结点的操作
            head->next=deleteDuplicates(temp);
        }
        return head;
    }
};

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode temp=head.next;
        if(head.val==temp.val){
            while(temp!=null&&head.val==temp.val){
                temp=temp.next;
            }
            head=deleteDuplicates(temp);
        }else{
            head.next=deleteDuplicates(temp);
        }
        return head;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.4 MB, 在所有 Java提交中击败了97.51%的用户