如何找到链表中的总项数？

9 浏览
0 Comments

如何找到链表中的总项数？

我有一个循环的链表，我想找出这个链表中元素的总数。如何实现？

0

3 答案

0 Comments

问题的出现原因是：在一个带有循环的链表中，需要找到链表中节点的总数，并且需要检测循环，以避免多次计算某些节点。

解决方法如下所示：

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

以上代码中，`count`方法用来计算链表中的节点数，`countInLoop`方法用来检测链表中的循环并计算循环中的节点数。

注意：由于链表带有循环，所以`temp`不会为`null`。请阅读问题中提到的问题描述。

0
0 Comments

链表中有两个部分：循环之前的部分和循环部分。我们可以通过Floyd循环检测算法来找到循环的起点和循环的长度。首先，使用慢指针和快指针进行循环检测，计算慢指针移动的步数s。一旦检测到相遇点，再次从相遇点开始循环，计算循环的长度y。

现在，从链表头开始，向前移动s-y步，到达节点N。最后，使用两个慢指针从节点N和节点M开始，移动t步，直到它们相遇。可以自己验证（或证明）它们相遇的位置就是链表的起始部分进入循环的位置。

因此，循环之前的部分有s-y+t+1个节点，循环部分有y个节点，总共有s+t+1个节点。

0
0 Comments

根据所给内容，我们可以整理出以下文章：

如何找到链表中的总项目数？

有一种解决方法是维护两个指针。第一个指针(*start)将始终指向起始节点，假设为节点A。另一个指针(*current)将被初始化为：current = start->next。现在，只需迭代每个节点，直到current指向start->next为止。并且不断递增一个计数器：numberOfNodes++。

代码如下：

public int countNumberOfItems(Node* start){

Node* current = start -> next;

int numberOfNodes = 1; //至少存在一个起始节点

while(current -> next != start){

numberOfNodes++;

current = current -> next;

}

return numberOfNodes;

}

在循环内部还应该添加current = current -> next来更新当前指针的位置。

谢谢，已经修正了错误。

还可以补充说明“起始节点”可以是链表中的任何节点。

0