提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode No.82 删除排序链表中的重复元素 II

排序
2023-03-20 14:55:30 时间

题目描述

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

返回同样按升序排列的结果链表。

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

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

提示： 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序排列

解题思路一

扫描一次链表，统计数字在链表中出现的次数，再次遍历链表，当节点的值出现的次数大于等于2时，将该节点删除

import utils.ListNode;
import java.util.HashMap;
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newHead=head;
        HashMap<Integer,Integer> map=new HashMap();
        while(head!=null){
            int value=head.val;
            if(map.get(value)==null){
                map.put(value,1);
            }else{
                map.put(value,map.get(value)+1);
            }
            head=head.next;
        }
        ListNode sentinel=new ListNode(0);
        sentinel.next=newHead;
        ListNode pre=sentinel,cur=newHead;
        while(cur!=null){
            if(map.get(cur.val)>=2){
                pre.next=cur.next;
                cur=cur.next;
            }else{
                pre=pre.next;
                cur=cur.next;
            }
        }
        return sentinel.next;
    }
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode node2=new ListNode(1);
        head.next=node2;
        ListNode node3=new ListNode(2);
        node2.next=node3;
        node3.next=null;
        Solution solution=new Solution();
        solution.deleteDuplicates(head);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。

空间复杂度：O(n)，其中 n 是链表的长度。

解题思路二

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哨兵节点（sentinel node）指向链表的头节点。

具体地，我们从指针 cur 指向链表的哑节点，随后开始对链表进行遍历。如果当前 cur.next 与 cur.next.next 对应的元素相同，那么我们就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 x，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 x 为止。此时，我们将链表中所有元素值为 x 的节点全部删除。

如果当前cur.next 与cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为 cur.next 的节点，那么我们就可以将cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的的哨兵节点的下一个节点 sentinel.next 即可。

细节

需要注意cur.next 以及 cur.next.next 可能为空节点，如果不加以判断，可能会产生运行错误。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode sentinel=new ListNode(0,head);
        ListNode cur=sentinel;
        while(cur.next!=null&&cur.next.next!=null){
            if(cur.next.val==cur.next.next.val){
                int x=cur.next.val;
                while(cur.next!=null&&cur.next.val==x){
                    cur.next=cur.next.next;
                }
            }else{
                cur=cur.next;
            }
        }
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode node2=new ListNode(1);
        head.next=node2;
        ListNode node3=new ListNode(2);
        node2.next=node3;
        node3.next=null;
        Solution solution=new Solution();
        solution.deleteDuplicates(head);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。

空间复杂度：O(1)。

相关文章