-2

我有一个循环的链表，我想找出这个列表中元素的总数。如何做到这一点？

4

5 回答 5

2

我能想到的一种解决方案是维护两个指针。第一个指针 (*start) 将始终指向起始节点，例如节点 A。另一个指针 (*current) 将被初始化为：current = start->next。

现在，只需使用 current -> next 迭代每个节点，直到它指向开始。并不断增加一个计数器：numberOfNodes++；

代码将如下所示：

public int countNumberOfItems(Node* start){
Node* current = start -> next;

int numberOfNodes = 1; //Atleast the starting node is there.

while(current->next != start){
   numberOfNodes++;
   current = current->next;
}
return numberOfNodes; 
}
于 2019-02-26T07:36:06.247 回答
0

您只想计算链表中的节点对吗？我在下面举了一个例子。但是在您的情况下，存在一个循环，因此您还需要检测到这一点，以免多次计算某些节点。我已经更正了我的答案，现在有一个普通的计数和循环计数（使用快速和慢速指针）。

static int count( Node n)  
{  
    int res = 1;  
    Node temp = n;  
    while (temp.next != n)  
    {  
        res++;  
        temp = temp.next;  
    }  
    return res;  
}  

static int countInLoop( Node list)  
{  
    Node s_pointer = list, f_pointer = list;  

    while (s_pointer !=null && f_pointer!=null && f_pointer.next!=null)  
    {  
        s_pointer = s_pointer.next;  
        f_pointer = f_pointer.next.next;  

        if (s_pointer == f_pointer)  
            return count(s_pointer);  
    }  

    return 0;  
}
于 2019-02-26T06:31:23.993 回答
0

假设列表x在循环之前有节点，在循环中有节点y。运行 Floyd 循环检测，计算慢步数s。一旦你检测到一个交汇点，再绕圈跑一次得到y.

现在，从列表头开始，s - y逐步到达节点N。最后，运行两个慢速指针N，M直到它们相遇，作为t步骤。说服自己（或更好地证明）他们在列表的初始部分进入循环的地方相遇。

因此，初始部分有s - y + t + 1节点，循环由y节点组成，给出s + t + 1总数。

于 2019-02-26T07:20:33.537 回答
0

首先使用弗洛伊德循环检测算法找到循环，并在检查循环时保持计数，一旦找到循环，然后打印相同的计数。

    function LinkedList() {
      let length = 0; 
      let head = null; 

      let Node = function(element) {
        this.element = element; 
        this.next = null;
      }

      this.head = function() {
        return head;
      };

    this.add = function(element) {
      let node = new Node(element);
      if(head === null){
          head = node;
      } else {
          let currentNode = head;
          while(currentNode.next) {
              currentNode = currentNode.next;
          }
          currentNode.next = node;
      }
    };
      this.detectLoopWithCount = function() {
        head.next.next.next.next.next.next.next.next = head; // make cycle
        let fastPtr = head;
        let slowPtr = head;
        let count = 0;
        while(slowPtr && fastPtr && fastPtr.next) {
          count++;
          slowPtr = slowPtr.next;
          fastPtr = fastPtr.next.next;
          if (slowPtr == fastPtr) {
            console.log("\n Bingo :-) Cycle found ..!! \n ");
            console.log('Total no. of elements = ', count);
            return;
          }
        }
      }
    
    }
    let mylist = new LinkedList();
      mylist.add('list1');
      mylist.add('list2');
      mylist.add('list3');
      mylist.add('list4');
      mylist.add('list5');
      mylist.add('list6');
      mylist.add('list7');
      mylist.add('list8');
      mylist.detectLoopWithCount();

于 2019-02-26T08:17:26.307 回答
0

有一个“慢”指针一次移动一个节点。有一个“快速”指针以两倍的速度移动，一次两个节点。

作为慢速和快速指针在具有 10 个节点的链表中移动的可视化：

1: |sf--------|
2: |-s-f------|
3: |--s--f----|
4: |---s---f--|
5: |----s----f|

在这一点上，有两件事之一是正确的：1) 链表不循环（用 fast != null && fast.next != null 检查）或 2) 它循环。假设它确实循环，让我们继续可视化：

6: |-f----s---|
7: |---f---s--|
8: |-----f--s-|
9: |-------f-s|
10: s == f

如果链表没有循环，则快速指针在 O(n/2) 时间完成竞争；我们可以删除常数并将其称为 O(n)。如果链表确实循环，则慢指针在整个链表中移动，并最终在 O(n) 时间等于快指针。

于 2019-02-26T08:48:23.153 回答