如何在单个遍历中找到单个链表的中间节点（如果未给出列表的长度） [英] How to find the middle node of a single linked list in a single traversal (if the length of the list is not given)

问题描述

我有一个问题语句，如：如何在一个遍历中找到单个链表的中间节点，而扭曲是我们不知道链表中节点的数量？

I have a problem statement like: "How to find the middle node of a singly linked list in only one traversal, and the twist is we don't know the number of nodes in the linked list?"

我有一个答案，例如获取一个向量，并开始推送所有节点的地址，当你遍历链表和增加一个计数器，直到到达列表的末尾 。因此，最后我们可以得到列表中的节点数，如果even（counter / 2）或者odd（counter / 2 + counter％2）给出中间节点号，这样我们可以得到 vectore.at（middlenodenumber）指向中间节点。

I have an answer like "take a vector and start pushing all the nodes' addresses as and when you are traversing the linked list and increment a counter till you reach the end of the list". So at the end we can get the number of nodes in the list and if even (counter/2) or if odd (counter/2 + counter%2) gives the middle node number and with this we can get vectore.at(middlenodenumber) points to the middle node".

这很好...但这是浪费内存存储所有

This is fine...but this is waste of memory storing all the address of a very large linked list! So how can we have a better solution?

推荐答案

以下是步骤：

• 取两个指针 * p1 和 * p2 指向链接的头
  list


• 开始循环并增加 * p2 ，2次with null checked）


• 如果 * p2 不为null，则增加 * p1 1次


• 当 * p2 达到null时，您会得到 * p1 中心

• Take two pointers *p1 and *p2 pointing to the head of linked list
• Start a loop and increment *p2, 2 times (with null checks)
• If *p2 is not null then increment *p1 1 time
• When *p2 reaches null; you have got the *p1 at the center

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

[Note: You can use iterators instead of pointer if you deal with container type linked list]

这篇关于如何在单个遍历中找到单个链表的中间节点（如果未给出列表的长度）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！