如何在单次遍历中找到单链表的中间节点（如果未给出列表长度）

Question

我有一个问题：如何在只遍历一次单链表的情况下找到中间节点，而且我们不知道链表中节点的数量？

我有一个答案：使用向量并在遍历链表时将所有节点的地址推入向量，并增加计数器直到到达列表的末尾。因此，最后我们可以得到列表中的节点数，如果是偶数则(counter/2)，如果是奇数则(counter/2 + counter%2)可以得到中间节点编号，然后使用vectore.at(middlenodenumber)指向中间节点。

这个方法可以实现...但是它浪费了大量的内存来存储一个非常大的链表的所有地址！那么我们该如何得到更好的解决方案呢？

- srinuvenu

Answer 1

以下是步骤：

• 取两个指针 *p1 和 *p2 指向链表头部
• 开始循环并且每次将 *p2 增加 2 次 (需要进行空值检查)
• 如果 *p2 不为空，则将 *p1 增加 1 次
• 当 *p2 到达空值时，*p1 就是链表的中心位置

[注意：如果你处理的是容器类型的链表，可以使用迭代器代替指针]

- iammilind

---

虽然这肯定是期望的答案，但我从未理解为什么它被认为是单次遍历。实际上，它是两个（或 1.5 个）并行遍历，并且指针/迭代器增量不比两个（1.5 个）串行遍历少。这避免了计数器，但没有减少任何遍历。 - xan

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的中间。

- Oswald

---

在第一次“advance b”之后，必须检查是否为空。否则会崩溃！ - iammilind

根据具体的问题陈述而定。如果给定列表有确切的中间位置，则其长度必须为奇数。然后您可以在循环之前“提前b”。 - MSalters

@iammilind 伪代码不会崩溃 :) 但你说得对，我用C++替换了代码，这样可以说明并解决你描述的问题。 - Oswald

如果链表中有偶数个节点，我们该如何处理它？如果在继续之前不检查空值，它会崩溃的。 - srinuvenu

Answer 3

你可以使用一个循环和两个迭代器，比如说it1和it2，其中你只在每隔一次循环迭代时增加it2。当it1到达列表的末尾时终止循环。此时it2将指向列表的中间元素。

- Björn Pollex

---

这是我的第一个想法，但它仍然是“只有一次遍历”吗？ - G B

是的，因为你只有一个循环。如果这是作业，我不知道它是否符合任务的要求，但实际上，这会遍历列表一次。 - Björn Pollex

真正的答案应该是这样的，因为当前的答案只在从循环结构考虑任务时形式上保持单遍历规则。但实际的扫描次数至少为1.5N。 - Arman

我没有看到我的答案和被接受的答案有任何区别，它们做的事情是一样的。 - Björn Pollex

Answer 4

// How to find the middle node of a single linked list in a single traversal
//     1. The length of the list is not given
//     2. If the number of nodes is even, there are two middle nodes,
//        return the first one.
Node* MiddleNode(Node* const head)
{
    if (!head)
    {
        return head;
    }

    Node* p1 = head, * p2 = head->next;

    while (p2 && p2->next)
    {
        p1 = p1->next;
        p2 = p2->next->next;
    }

    return p1;
}

- Peter Lee

Answer 5

SLNode* mid(SLNode *head) 

{

SLNode *one = head;

SLNode *two = head;


    while(one != nullptr) {
        one = one->next;
        two = two->next;
        if(one != nullptr) {
            one = one->next;
            //two = two->next;
        }
    }
    return two;
}

试一下这段代码

- RajatRusty

Answer 6

试试这个：
你有两个指针。一个指向中间，另一个指向末尾，两者在开始时都指向列表的开头。每隔一秒钟成功增加一次末尾指针，就将中间指针增加一次，直到末尾指针到达末尾。

- atoMerz

Answer 7

使用两个指针。第一个指针移动两个节点，第二个指针移动一个节点。当第一个指针到达末尾时，第二个指针将指向中间位置。

- Jeeva