如何统计我的链表中有多少个不同的节点？

Question

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

我曾尝试与此代码，但它不工作：

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); 

这是supose给我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

你j循环没有踏node前开始i - 它总是比较相同的一对节点，因此没有任何功能。

你需要的东西，如：

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

Answer 2

使用设置

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

这取决于你实施的hashCode并在节点级等于，或者你可以使用TreeSet的和一个比较器。

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 3

您可以使用Set。

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

这不使用泛型，因为我不知道你有什么类型的getInfo。或者，如果你不能使用一个集合，你应该尝试摆脱你的'索引'变量（我和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 4

第一个问题：

如果你的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 5

你周围的i循环您j循环第一次不执行任何操作（因为它从0开始，并继续同时j < i它不是），所以你离开distinct设置为true没有任何与任何比较。

尝试在1