如何在单个遍历中找到单个链表的中间节点(如果未给出列表的长度)

Question

我有一个问题陈述,如:"如何只在一次遍历中找到单链表的中间节点,而扭曲是我们不知道链表中的节点数？"

我有一个答案,比如"当你遍历链表并递增计数器直到你到达列表的末尾时,取一个向量并开始推送所有节点的地址".所以最后我们可以得到列表中的节点数量,如果是偶数(计数器/ 2)或者奇数(计数器/ 2 +计数器%2)给出中间节点数,那么我们可以得到vectore.at(middlenodenumber)点到中间节点".

这很好......但这是浪费内存存储一个非常大的链表的所有地址!那么我们如何才能有更好的解决方案呢？

Answer 1

以下是步骤:

• 拿两个指针*p1和*p2指向链表的头
• 开始循环并增加*p22次(使用空检查)
• 如果*p2不为null则增加*p11次
• 当*p2达到null时; 你有*p1中心位置

[注意:如果处理容器类型链表,可以使用迭代器而不是指针]

Answer 2

说你有std::list<T> l.

std::list<T>::iterator i = l.begin();
std::list<T>::iterator m = l.begin();
bool even = true;
while (i != list.end())
{
  if (even) ++m;
  ++i;
  even = !even;
}

现在m指向中间l.