LeetCode刷题:面试题 02.01. 移除重复节点

发布时间:2024年01月07日

题目:

是否独立完成:算是,但是使用自己的办法时间复杂度会超标

解题思路:

1.双循环嵌套,定义快慢节点,双层嵌套循环,如果值一样则剔除,但是时间复杂度为O(n2)会超标

2.哈希表,利用set接口的特点,不能存储重复的值

?解题代码:

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null ){return null;}//判断链表是否为空
   
    Set<Integer> box = new HashSet<Integer>();
      box.add(head.val);//将头结点的值存入哈希表中

     ListNode pre = head;//创建一个节点指向头结点

    while(pre.next!=null){//不能pre!=null,因为下面还会创建节点指向pre.next,如果pre!=null会报空指针异常

        ListNode cur = pre.next;//在循环内部定义快指针每循环一次,cur可以随着pre的变化而变化(个人理解不一定正确)
      
        if(box.add(cur.val)){//如果set添加了pre后面节点的值那么证明这个点不是重复的
            
            pre=pre.next;//则移动pre往后一格
           
        }else{
             pre.next=cur.next;//如果没有添加证明这个点是添加过的,则跳过这个点
          
        }
      
    }
    
    return head;
}
}

文章来源:https://blog.csdn.net/weixin_46139028/article/details/135441620
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。