如何计算我的链接列表中有多少不同的节点

Question

我创建了自己的Node类和LinkedList类，我想构建一个函数来计算LinkedList中有多少不同的Node。

我尝试过这个代码，但它不起作用：

for (int i = 0; i < quantityOfNode(); i++) {
    boolean isDistinct = true;
    for (int j = 0; j < i; j++) {
        if (node.getInfo().equals(node.getNext().getInfo())) {
            isDistinct = false;
        }
    }
    if (isDistinct) {
        nbDistinct++;
    }
    if (node.getNext().getNext() != null) {
        node= node.getNext();
    }
}

示例：

        list.add(3);
    list.add(2);
    list.add(5);
    list.add(3);
    list.add(3);
    list.add(8);

这给了我4个不同的节点，但我得到了5个，因为节点3是的2倍

现在我已经尝试在我的j循环中使用第二个节点，对于相同的输入，它现在给我2而不是4

这是我尝试过但仍然不起作用的新代码：

            for (int i = 0; i < quantityOfNode(); i++) {
            boolean isDistinct = true;
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;
                }
                if (node2.getNext() != null) {
                    node2 = node2.getNext();
                }
            }
            if (isDistinct) {
                nbDistinct++;
            }
            if (node.getNext() != null) {
                node= node.getNext();
            }
        }

Answer 1

第一个问题：

如果你的for循环是这样写的，它不会超过链接列表的长度：

for (int i = 0; i < length(); i++) {

那你为什么需要这个？

            if (node.getNext().getNext() != null) {
                node= node.getNext();
            }

特别是，这段代码可能意味着，刚好在结束之前的节点将被求值两次，因为它之后的节点是null。它不一定会让你的算法出错，但它闻起来很臭，我不喜欢它

第二个问题：

            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node.getNext().getInfo())) {
                    isDistinct = false;
                }
            }

这是一种计算重复项的错误方法，因为您没有存储和提前比较第二个节点的位置。试试之类的东西

            Node node2 = firstNode(); //idk what method gets the first node :)
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;
                    break; //optimization, stop as soon as we find a duplicate
                }
                node2 = node2.GetNext();
            }

最后，每当遇到不起作用的代码时，请附加一个调试器，逐步检查它，并注意代码何时没有达到预期效果。这将通过少量观察快速解决所有逻辑错误。即使您没有访问调试器的权限，也可以使用print语句打印各种变量的值，以及某些代码分支何时执行，并与您预期的结果进行比较。

Answer 2

您可以使用Set。

Set set = new HashSet();
Node cur = list.head;
while(cur != null) {
    set.add(cur.getInfo());
    cur = cur.getNext();
}
return set.size();

这不使用泛型，因为我不知道getInfo有什么类型。

或者，如果不能使用集合，则应该尝试去掉"索引"变量(i和j(。您确实希望将应用程序逻辑集中在实际拥有的内容上，而不是隐式计算的值。您希望在当前节点变为空时停止，而不是在您已经前进了一定次数时停止。如果这不符合逻辑，请告诉我。

对于每个节点，请检查其前面的节点以查看该节点是否存在。我每次都从头开始，因为我不知道你是否有双重链接。无论哪种方式，它的复杂性都是一样的，但在排序列表中，这不是最佳的。

Node cur = list.head; // for each node
int nbDistinct = 0;
while(cur != null) { // go until we're out of nodes
    Node check = list.head; // check the first node
    boolean isDistinct = true; // assume distinct
    while(check != cur && isDistinct) { // stop if we found a match OR if our checker caught up to our current node
        isDistinct |= !check.getInfo().equals(cur.getInfo()); // essentially "if(check.getInfo().equals(cur.getInfo()) isDistinct = true;"
        check = check.getNext(); // advance the checker
    }
    if(isDistinct) nbDistinct++;
    cur = cur.getNext(); // advance the current node
}

Answer 3

您的j循环并没有将node向前推进-它总是比较同一对节点，因此没有任何功能。

你需要这样的东西：

...
Node earlierNode = rootNode;
for (int j = 0; j < i; j++) {
    if (earlierNode.getInfo().equals(node.getInfo())) {
        isDistinct = false;
    }
    earlierNode = earlierNode.getNext();
}
...

Answer 4

使用集合

Set<Node> mySet = new HashSet<Node>(list);
answer = mySet.size();

这取决于您在节点类中实现hashCode和equals，或者您可以使用TreeSet和Comparator。

Comparator<Node> myComparator = new MyCustomComparator();// you have to define your comparator.
Set<Node> mySet = new TreeSet<Node>(myComparator);
mySet.addAll(list);
answer = mySet.size();

Answer 5

第一次在i循环中，j循环什么都不做(因为它从0开始，在j < i时继续，而不是(，所以您将distinct设置为true，而不将任何内容与任何内容进行比较。

尝试在1启动i。