如何在一次迭代中走到奇异链表的中间？

Question

最近我被问到一个问题,在一个单独的链表中我们如何在一次迭代中进入列表的中间位置.

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

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

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

对此,它也应该返回指向B的地址

有一个解决方案,两个指针一个移动一次,其他移动两次,但它似乎没有在这里工作

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

如果有人之前做过这个,请帮忙.

Answer 1

基本算法是

0拿两个指针

1使两者都指向第一个节点

2首先使用两个节点递增,如果成功,则先递增,然后在第二个节点前面遍历一个节点

3当第二个到达结束时,第一个将在中间.

更新:

它肯定会在奇怪的情况下工作,因为即使你需要再检查一个条件,如果第一个点允许下一个移动而不是下一个接下来那么两个指针都在中间你需要决定哪个作为中间

Answer 2

除非您成功地将p2 提前两次,否则无法前进p1 ; 否则,如果列表长度为2,则最终两者都指向末尾(并且您指示甚至长度列表应该朝向开头舍入).

所以:

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