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

Question

我用java设计了自己的单链表数据结构。现在我要定义一个具有特定行为的函数。我将这个函数命名为“PurgeList”。这个函数应该删除每个重复的节点(节点具有相同的内容)来自链表，至少我希望该列表本身只保留一个包含该内容的节点。例如，如果节点中保存的当前内容是顺序的:

1 , 2 , 3 , 4 , 1 , 4 , 5

执行具有上述行为的函数后，列表必须形成:

1 , 2 , 3 , 4 , 5

示例代码:

1- Class Node

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- Class List

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