比較循環鏈表等於方法

Question

public class LinkedList { 

Object contents; 
LinkedList next = null; 

public boolean equals(Object item) { 
    return (this == item) || ((item instanceof LinkedList) && this.equals((LinkedList)item)); 
    } 

public boolean equals(LinkedList item) { 
    return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
} 

} 

public class myUtil{ 
    public static boolean equals(Object x, Object y) { 
    return (x == y) || (x != null && x.equals(y)); 
} 
} 

main(){ 
LinkedList myList = new LinkedList(); 
myList.next = new LinkedList(); 
LinkedList head = myList.next; 
myList.next = head; 
} 

我想我已經在這裏創建了一個循環鏈表。所以我所做的是覆蓋等於方法，以確保循環引用處理：

由於某種原因LinkedList.equals似乎不會返回...是因爲我的循環鏈表，或者我缺少一些條件？

Answer 1

此代碼的主要問題是您的比較不會終止於循環引用，並且如果所有內容字段都相等，將永遠循環。它會一直持續到下一個比較，並且由於下一個項目總是在那裏（因爲它是一個圓圈），這將永遠持續下去。

myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 

爲了解決這個問題，最簡單的方法是添加一個布爾私人「訪問」字段以每個列表項。比較後，在每個項目上設置訪問權限。如果兩者都沒有訪問和相同，然後繼續。如果只訪問了一個，你的列表就不一樣了。如果兩者都被訪問過，那麼您已經比較了可用的整個列表。一般來說，在你的列表中有循環是一個壞主意，並且存在專門用於檢測它們的算法。這可能是一個令人困惑的話題。這裏是環路檢測的coverage，可以幫助您進一步瞭解問題。請記住，如果您使用visited字段，則必須使用equals（）中的另一個循環取消所有這些字段以允許其再次運行。

另一方面，您不會初始化您的列表節點的內容字段以進行測試。這裏沒關係，因爲它們被初始化爲null，但通常明確初始化所有字段是一個好習慣。

一般而言，您也不需要equals(Object item)覆蓋。嘗試

public boolean equals(LinkedList item){ 
    if (this == item){ 
    return true; // It's the same object 
    } 

    // Add some null checks here, I'm lazy 

    if (this.visited && item.visited && this.contents.equals(item.contents){ 
    this.visited = false; //Unset 
    item.visited = false; 
    return true; 
    } 
    if (this.visited && !item.visited){ 
     this.visited = false; 
     return false; 
    } 
    if (!this.visited && item.visited){ 
     item.visited = false; 
     return false; 
    } 
    if (!this.visited && !item.visited && this.visited.contents.equals(item.contents){ 
     this.visited = true; 
     item.visited = true; 
     boolean ret = this.next.equals(item.next); 
     this.visited = false; 
     item.visited = false; 
     return ret; 
    } 

    // Contents not equal 
    return false; 
} 

這回溯並取消了一些基本的遞歸。我顯然還沒有編譯這一點，但這是它的精神，我認爲（我希望不會有太多的錯誤）

Answer 2

return myUtil.equals(this.contents, item.contents) 
&& myUtil.equals(this.next, item.next); 

我會想象這是你的，你懷疑的問題，當您執行的& &即myUtil.equals(this.next, item.next);第二表達你進入執行這條線的myUtil.equals方法：

return (x == y) || (x != null && x.equals(y)); 

它依次使用x的.equals（）方法，它將重複其item.next等等的過程，因爲您有一個循環鏈接列表。

Answer 3

兩個問題，首先你沒有一個循環鏈表。以下代碼創建2個列表，list1.next = list2，list2.next = null。沒有創建圈子。

LinkedList myList = new LinkedList(); 
myList.next = new LinkedList(); 
LinkedList head = myList.next; 
myList.next = head; 

第二，如果你確實有一個循環鏈表，下面會因爲沒有結束條件達到了，這是因爲在循環鏈接鏈接，next不應該是null產生無限循環。

public boolean equals(Object item) { 
    return (this == item) || ((item instanceof LinkedList) &&  
    this.equals((LinkedList)item)); 
} 

public boolean equals(LinkedList item) { 
    return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
} 

爲了有效地做到這一點，你需要提供一些機制來迭代列表以非循環方式，即使這個機制是私營和不暴露給其他用戶。一種方法是將單個節點標記爲「根」。

Answer 4

這將導致一個無限循環，這是因爲在代碼：

public static boolean equals(Object x, Object y) { 
     return (x == y) || (x != null && x.equals(y)); 
    } 

的x.equals(y)將再次調用：

public boolean equals(LinkedList item) { 
     return myUtil.equals(this.contents, item.contents) 
       && myUtil.equals(this.next, item.next); 
    } 

但是，如果您正在執行myList1.equals(myList1)，你不會得到一個無限循環，因爲在myUtils.equals()的(x==y)將返回true如此無限升如果您比較相同的物體，則不會發生這種情況。

但是，當你比較不同的對象時，你將進入一個無限循環。

這不是一個循環列表問題，這是因爲你選擇的代碼設計。