我有这样的问题陈述:“如何在一次遍历中找到单向链表的中间节点，问题是我们不知道链表中的节点数？”
我有一个答案，比如“获取一个 vector ，并在遍历链表时开始推送所有节点的地址，并递增一个计数器，直到到达链表的末尾”。所以最后我们可以获得列表中的节点数，如果偶数 (counter/2) 或奇数 (counter/2 + counter%2) 给出中间节点号，我们可以得到 vectore。 at(middlenodenumber) 指向中间节点"。
这很好......但是这是浪费内存来存储一个非常大的链表的所有地址!那么如何才能有更好的解决方案呢？
最佳答案
步骤如下:
- 取两个指针
*p1和*p2指向链表的头部 列表 - 开始一个循环并递增
*p2，2 次(带空检查) - 如果
*p2不为空则将*p1递增 1 次 - 当
*p2为null时；你在中心得到了*p1
[注意:处理容器类型链表可以用迭代器代替指针]
关于c++ - 如何在单次遍历中找到单链表的中间节点(如果不给出链表长度)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6703880/