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

2022-01-01 00:00:00 linked-list c++

我有一个问题陈述，如:如何仅在一次遍历中找到单向链表的中间节点，而问题是我们不知道链表中的节点数?"

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?"

我有一个答案，比如当你遍历链表并增加一个计数器直到你到达链表的末尾时，取一个向量并开始推送所有节点的地址".所以最后我们可以得到列表中的节点数，如果偶数 (counter/2) 或奇数 (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 指向链接的头部列表
  • 开始循环并递增 *p2，2 次(带空检查)
  • 如果 *p2 不为空，则将 *p1 增加 1 次
  • 当 *p2 达到空值时；你有 *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]

相关文章