如何在一个迭代中单独链接列表的中间？ [英] how to go the middle of the singularly linked list in one iteration?

问题描述

最近我被问到一个问题，在一个单一的链表中，我们如何在一个迭代中到列表的中间。

  A  - > B  - > C  - > D（偶数节点）
  

为此，它应该返回指向B的地址

  A  - > B  - > C（奇数节点）
  

为此也应该返回指向B的地址

有一个解决方案是采取两个指针，一次移动，另一个移动两次，但在这里似乎不起作用

  LinkedList p1，p2; 
 
 while（p2.next！= null）
 {
 p1 = p1.next; 
 p2 = p2.next.next; 
 
} 
 
 System.out.print（中间的节点+ p1.data）; //这不能给出正确的结果在奇数甚至
  

请帮助，如果有人以前这样做。

解决方案

除非成功高级p2两次，否则您不能提前执行p1否则，列表长度为2，最后两者都指向最后（并且您指出，长度列表应该向左开始）。

所以： p>

  while（p2.next！= null）{
 p2 = p2.next; 
 if（p2.next！= null）{
 p2 = p2.next; 
 p1 = p1.next; 
} 
} 
  

Recently I have been asked one question that in a singularly linked list how do we go to the middle of the list in one iteration.

A --> B --> C --> D (even nodes)

for this it should return address which points to B

A --> B --> C (odd nodes)

for this also it should return address which points to B

There is one solution of taking two pointers one moves one time and other moves two times but it does not seem working here

LinkedList p1,p2;

while(p2.next != null)
{
    p1 = p1.next;
    p2 = p2.next.next;

}

System.out.print("middle of the node" + p1.data); //This does not give accurate result in odd and even

Please help if anyone has did this before.

解决方案

You can't advance p1 unless you successfully advanced p2 twice; otherwise, with a list length of 2 you end up with both pointing at the end (and you indicated even length lists should round toward the beginning).

So:

while ( p2.next != null ) {
    p2 = p2.next;
    if (p2.next != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
}

这篇关于如何在一个迭代中单独链接列表的中间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！