0

我创建了自己的 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();
            }
        }
4

5 回答 5

2

你可以使用一个集合。

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
}
于 2013-03-27T23:15:17.337 回答
2

第一个问题：

如果你的 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语句来打印各种变量的值以及某些代码分支何时执行并与您预期的情况进行比较。

于 2013-03-27T23:15:31.240 回答
1

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

你需要类似的东西：

...
Node earlierNode = rootNode;
for (int j = 0; j < i; j++) {
    if (earlierNode.getInfo().equals(node.getInfo())) {
        isDistinct = false;
    }
    earlierNode = earlierNode.getNext();
}
...
于 2013-03-27T23:35:20.923 回答
0

使用一套

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();
于 2013-03-27T23:14:32.040 回答
0

你第一次在i循环中你的j循环什么都不做（因为它从 0 开始并在j < i它不是的时候继续）所以你保持distinct设置为真而不将任何东西与任何东西进行比较。

尝试从i1 开始。

于 2013-03-27T23:20:39.247 回答