如何从链表中删除重复的节点？

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