爲什麼我無法從鏈接列表中刪除重複項？

 /* 
DEFINITIONS 

public class ListNode { 
     int val; 
     ListNode next; 
     public ListNode(int x){ 
      val = x; 
      next = null; 
     } 

    } 


    public class LinkedList { 
     ListNode head; 
    } 
    */ 


    public void removeDups(){ 
     ListNode head = this.head; 
     if(head == null) return; 

     HashSet<ListNode> set = new HashSet<>(); 
     set.add(head); 
     while(head.next != null){ 
      if(set.contains(head.next)){ 
       head.next = head.next.next; 
      } else{ 
       set.add(head.next); 
       head = head.next; 
      } 
     } 
    }

我應該刪除未排序列表中的重複項，但它不能在Java中工作。爲什麼我無法從鏈接列表中刪除重複項？

1->2->4->9->9->4應該返回1->2->4->9，但它仍然會返回1->2->4->9->9->4

問題是什麼？我清楚地將所有節點插入到一個哈希集並檢查它是否包含，但不知道發生了什麼？

來源

2017-04-21 sssszzzzzzssszzz

您正在刪除重複節點，而不是您發佈代碼中的重複值節點。

/* 
DEFINITIONS 

public class ListNode { 
    int val; 
    ListNode next; 
    public ListNode(int x){ 
     val = x; 
     next = null; 
    } 

} 


public class LinkedList { 
    ListNode head; 
} 
*/ 


public void removeDups(){ 
    ListNode head = this.head; 
    if(head == null) return; 

    HashSet<Integer> set = new HashSet<Integer>(); 
    set.add(head.val); 
    while(head.next != null){ 
     if(set.contains(head.next.val)){ 
      head.next = head.next.next; 
     } else{ 
      set.add(head.next.val); 
      head = head.next; 
     } 
    } 
}

來源

2017-04-21 09:36:32 v78

您試圖檢查set包含ListNode，但你沒有在ListNode類重寫equals方法。嘗試覆蓋它，或者添加值來設置，而不是整個節點，它會工作，因爲值是簡單的整數。

你也應該重寫hashCode方法，如覆蓋equals時，你應該總是做 - 感謝安迪·特納

來源

2017-04-21 09:38:40 Shadov

請注意，因爲OP使用'HashSet'，所以您還需要重寫'hashCode（）'，否則具有相同值的節點可能甚至不會被比較。當然，如果你重寫一個，你應該重寫這兩個，但是值得明確地說明。 –

只需添加到v78's answer，準確描述爲什麼它不目前的工作的理由：

或者，你可以實現在ListNode類，這將允許節點被視爲相等如果他們有相同valequals和hashCode：

int hashCode() { return val; } 

boolean equals(Object other) { 
    if (other == this) return true; 
    return (other instanceof ListNode) 
     && val == ((ListNode) other).val; 
}

來源

2017-04-21 09:53:13

爲什麼我無法從鏈接列表中刪除重複項？

回答

相關問題