how to go the middle of the singularly linked list in one iteration?

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.

The basic algorithm would be

0 Take two pointers

1 Make both pointing to first node

2 Increment first with two node and first if its successful then traverse second to one node ahead

3 when second reaches end first one would be at middle.

Update:

It will definitely work in odd case, for even case you need to check one more condition if first point is allowed to move next but not next to next then both pointers will be at middle you need to decide which to take as middle

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;
    }
}

I know you've already accepted an answer, but this whole question sounds like an exercise in cleverness rather than an attempt to get the correct solution. Why would you do something in O(n) when you can do it in O(n/2)?

EDIT: This used to assert O(1) performance, and that is simply not correct. Thanks to ysth for pointing that out.

In practice, you would do this in zero iterations:

LinkedList list = ...
int size = list.size();
int middle = (size / 2) + (size % 2 == 0 ? 0 : 1) - 1; //index of middle item
Object o = list.get(middle);  //or ListIterator it = list.listIterator(middle);

The solution of taking two pointers and one moves a half the rate should work fine. Most likely it is not the solution but your actual implementation that is the problem. Post more details of your implementation.

static ListElement findMiddle(ListElement head){
    ListElement slower = head;
    ListElement faster = head;
    while(faster.next != null && faster.next.next !=null ){
        faster = faster.next.next;
        slower = slower.next;
    } 
    return slower;
}

public static Node middle(Node head){

    Node slow=head,fast=head;
    while(fast!=null& fast.next!=null && fast.next.next!=null){

         slow=slow.next;
         fast=fast.next.next;                   
    } 


    if(fast!=null && fast.next!=null){
        slow=slow.next;
    }


    return slow;

} 

public ListNode middleNode(ListNode head) {
    if(head == null) return head;

    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow;
}