如何從鏈表中刪除重複的節點？

Question

我在java.Now中設計了我自己的單鏈表數據結構，我將要定義一個具有特定行爲的函數。我將這個函數命名爲「PurgeList」。該函數應該刪除每個重複的節點相同的內容），並且至少我希望列表本身只保留一個包含該內容的節點。例如，如果節點中保存的當前內容是順序的：

1，2，3 ，4，1，4，5

與所提到的行爲的函數執行後，該列表必須塑造成：

1，2，3，4，5

例代碼：

1-類節點

public class Node { 
Object Element; 
Node Link; 

public Node() { 
    this(null,null); 
} 

public Node(Object Element, Node Link) { 
    this.Element = Element; 
    this.Link = Link; 
} 
} 

2-班級列表

import java.util.Scanner; 
public class List { 
int Size; 
Node FirstNode; 
Scanner UserInfo = new Scanner(System.in); 
Scanner UserInput = new Scanner(System.in); 
Node LastNode; 
public List() { 
    FirstNode = null; 
    Size = 1; 
} 
public void PurgeList() { 
    Node temp1 = FirstNode; 
    while (temp1 != null) { 
     Node temp2 = temp1; 
     while (temp2.Link != null) 
      if (temp1.Element.equals(temp2.Link.Element)) 
       temp2 = temp2.Link; 
      else 
       temp2=temp2.Link; 
     temp1=temp1.Link; 
    } 
} 
public boolean IsEmpty() { 
    return FirstNode == null; 
} 
public int SizeOf() { 
    return Size; 
} 
public void InsertArbitrary() { 
    System.out.print("Where To Put Node : "); 
    int Location = UserInput.nextInt(); 
    if (Location > Size) { 
     System.out.println("Invalid Input.Try again"); 
     return; 
    } else if (Location < 0) { 
     System.out.println("Invalid Input.Try again"); 
     return; 
    } else if (Location == 1) { 
     System.out 
       .printf("Enter something to save in Node %d : ", Location); 
     Object Element = UserInfo.nextLine(); 
     FirstNode = new Node(Element, FirstNode); 
    } else if (Location > 0 && Location <= Size) { 
     System.out 
       .printf("Enter something to save in Node %d : ", Location); 
     Object Element = UserInfo.nextLine(); 
     Node CurrentNode = FirstNode; 
     for (int i = 1; i <= Location - 2; i++) { 
      CurrentNode = CurrentNode.Link; 
     } 
     Node NewNode = new Node(Element, CurrentNode.Link); 
     CurrentNode.Link = NewNode; 
    } else { 
     System.out.println("Invalid Number . Try again."); 
     return; 
    } 
    Size++; 
} 

public void ShowOff() { 
    Node Temp; 
    Temp = FirstNode; 
    int number = 1; 

    while (Temp != null) { 
     System.out.println(Temp.Element); 
     Temp = Temp.Link; 
     number++; 
    } 
} 
protected boolean ListIsEmpty() { 
    return FirstNode == null; 
} 
} 

我複製了我執行其他函數的更多細節。我也追蹤了我的程序，但沒有發現我的邏輯錯誤。請幫我解決這個問題。提前感謝。

Answer 1

當您找到重複項時，您不會刪除該節點。

而不是

while (temp2.Link != null) 
     if (temp1.Element.equals(temp2.Link.Element)) 
      temp2 = temp2.Link; 
     else 
      temp2=temp2.Link; 

嘗試

 while (temp2.Link != null) { 
      if (temp1.Element.equals(temp2.Link.Element)) 
       temp2.Link = temp2.Link.Link; 
      else 
       temp2=temp2.Link; 
     } 

你應該儘量想不同的情況，以測試它做好。我試着用這個：

public static void main(String[] args) { 
    List list = new List(); 
    for (int i=0; i<5; ++i) { 
     list.InsertArbitrary(); 
    } 
    list.ShowOff(); 
    list.PurgeList(); 
    System.out.println("------------------"); 
    list.ShowOff(); 
} 

$ java List 
Where To Put Node : 1 
Enter something to save in Node 1 : 1 
Where To Put Node : 2 
Enter something to save in Node 2 : 2 
Where To Put Node : 3 
Enter something to save in Node 3 : 3 
Where To Put Node : 4 
Enter something to save in Node 4 : 1 
Where To Put Node : 5 
Enter something to save in Node 5 : 5 
1 
2 
3 
1 
5 
------------------ 
1 
2 
3 
5 

$ java List 
Where To Put Node : 1 
Enter something to save in Node 1 : 1 
Where To Put Node : 2 
Enter something to save in Node 2 : 1 
Where To Put Node : 3 
Enter something to save in Node 3 : 1 
Where To Put Node : 4 
Enter something to save in Node 4 : 1 
Where To Put Node : 5 
Enter something to save in Node 5 : 1 
1 
1 
1 
1 
1 
------------------ 
1 

Answer 2

你需要使用Set Collection來避免重複的值。 這裏是一個例子The Set interface