如何統計我的鏈表中有多少個不同的節點？

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