Finding the middle element of Singly Linked List

Question

Here is my code:

    public void findMiddlePos() {
    int pos = 1;
    Node pointerOne = first;
    Node pointerTwo = first;
    while(pointerOne.next.next != null) {
        pointerOne = pointerOne.next.next;
        pointerTwo = pointerTwo.next;
        pos++;
    }
    System.out.println("The middle element is : ");
    if((pos % 2) == 1)
        pointerTwo.printNode();
    else 
        pointerTwo.next.printNode();

}

Is it an efficient way? Also, I am doubtful about this line while(pointerOne.next.next != null). Previously, I was just using this condition in while loop: pointerOne.next != null, but I was getting Null pointer exception so shifter to earlier one.

Thanks.

Answer 1

I'm no Java programmer, so this merely regards the algorithm.

while(pointerOne.next.next != null) {
    pointerOne = pointerOne.next.next;
    pointerTwo = pointerTwo.next;
    pos++;
}

What happens if pointerOne.next is null? I'm guessing you'd need this:

while(pointerOne != null && pointerOne.next != null) {

I don't know if there is some shorthand for this in Java.

I also fail to see the purpose of the final if. Assume that you have a list with 3 elements. Then, after the loop, you'll have

pointerOne = first.next.next; // i.e., pointerOne = last
pointerTwo = first.next;
pos = 2;

So, pointerTwo points to the second (i.e., middle) element. But then your if will printout the successor of pointerTwo, which is the third element of a three-element list, so definitely not the middle one.

Lastly, I'd suggest using more descriptive names. For example, ptrLast and ptrMiddle, instead of pointerOne and pointerTwo. It makes your code more readable to others (which also includes you, after a few months).

One comment on your previous attempt:

Is it an efficient way? Also, I am doubtful about this line while(pointerOne.next.next != null). Previously, I was just using this condition in while loop: pointerOne.next != null, but I was getting Null pointer exception so shifter to earlier one.

If the length of your list is even, you'll get pointerOne == null at some point, so pointerOne.next will result in an error. But, similarly, if the length of your list is odd, you'll get pointerOne.next == null at some point, so pointerOne.next.next will result in an error.

Since you're jumping by two nodes at a time, you need to make sure that they are both non-null. Hence the condition I've put above.

Answer 2

If you were getting a NPE with pointerOne.next and not pointerOne.next.next then something else is going on. You should not be able to get to .next.next without having a connection to .next, it is a "linked" list after all. Regarding the code supplied, the methodology used would find the center of an oddly sized list, but the current implementation is buggy as described in other posts. Furthermore, I would argue that an evenly sized list does not have a single center as would be indicated by the implementation provided.

Regarding middle position and assuming you have implemented this linked list yourself, you should internally manage a size variable as any good Collection would. Thus, you would know the overall size of the collection and could determine the middle index(s) and .next to it/them.