GFG无序链表去重问题：ArrayList超时换HashSet解决

安全阿岳

2026-8-11

问题分析与解决方案

核心原因

你遇到的超时问题确实是因为ArrayList.contains()方法的低效性：

ArrayList.contains()会从头遍历整个列表来检查元素是否存在，时间复杂度为O(n)。当链表节点数量很大时，每次检查都要遍历已存储的所有元素，整体时间复杂度会达到O(n²)，在大数据量测试用例下必然超时。
HashSet.contains()是基于哈希表实现的，查找操作的平均时间复杂度为O(1)，即使处理大量数据，整体时间复杂度也能维持在O(n)，不会触发超时。

修改后的代码

把ArrayList替换为HashSet即可，逻辑完全不变，仅需修改集合类型：

class Solution
{
    //Function to remove duplicates from unsorted linked list.
    public Node removeDuplicates(Node head) 
    {
         if (head == null) return null;
         
         Node prev = head;
         Node temp = head.next;
         HashSet<Integer> seen = new HashSet<>();
         seen.add(head.data);
         
         while(temp != null){
             if(seen.contains(temp.data)){
                 prev.next = temp.next;   
                 temp = temp.next;
             }
             else{
                 seen.add(temp.data);
                 prev = prev.next;
                 temp = temp.next;
             }
         }
         return head;
    }
}