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


给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5


示例 2:

输入: 1->1->1->2->3
输出: 2->3


思路一:使用map记录节点值将所有出现次数大于1的值删除。需要遍历两次并且使用散列表辅助空间。

ListNode deleteDuplicates(ListNode head) {
        Map<Integer,Boolean> map=new HashMap<>();
        ListNode tem=head;
        while(tem!=null){
            if(map.containsKey(tem.val)){
                map.put(tem.val,true);
            }else{
                map.put(tem.val,false);
            }
            tem=tem.next;
        }
        ListNode node=new ListNode(0);
        node.next=head;
        ListNode res=node;
        while(node.next!=null){
            if(map.get(node.next.val))
            {
                node.next=node.next.next;
            }else {
                node=node.next;
            }
        }
        return res.next;
    }
执行用时 :5 ms, 在所有 java 提交中击败了5.79%的用户
内存消耗 :36.6 MB, 在所有 java 提交中击败了62.44%的用户
嗯。。。慢的一批。。尝试其他思路。。

思路二:对于每一个节点比较 它后面两个元素是否相等,如果相等继续判断第三,四,五...个是否相等,然后删除这些节点。如果不相等,往后遍历。
  public ListNode deleteDuplicates(ListNode head) {
        ListNode lshead = new ListNode(0);//接一个头结点
        lshead.next = head;
        ListNode tem = lshead;//正在遍历的节点
        ListNode prenode = tem.next;//遍历节点的后继
        ListNode nextnode = null;//遍历节点的后继的后继
        if (prenode != null) {
            nextnode = prenode.next;
        }
       while (prenode != null && nextnode != null) {
            while (nextnode != null&&prenode.val == nextnode.val) {//相等则nextnode继续往后遍历
                nextnode = nextnode.next;
                tem.next = nextnode;
            }
            if(nextnode!=null){//删除重复节点
                prenode = tem.next;
                nextnode = prenode.next;
            }
            while (nextnode != null && prenode.val != nextnode.val) {//不相等往后遍历
                tem = tem.next;
                prenode = tem.next;
                nextnode = tem.next.next;

            }
        }
        return lshead.next;
    }
执行用时 :1 ms, 在所有 java 提交中击败了98.53%的用户
内存消耗 :36.9 MB, 在所有 java 提交中击败了59.25%的用户
 
  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2019-12-03 05:54:23
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论

    强强鹏
    写的不戳!
    喂喂喂
    你好(*´▽`)ノノ