CODEWITHSUNDEEP
algorithmlinked-list
Arunachalam
Arunachalam

Reputation: 6037

how to find middle node in singly linked list without traversal?

how to find middle node in singly linked list without traversal ?

is it possible in first place ?

In One traversal I Use the traditional method of using 2 pointers one which jump's 2 positions and other which jump's one position ..is there any other approach to find middle node in one traversal

Upvotes: 7

Views: 23854

Answers (5)

codewarrior
codewarrior

Reputation: 1034

public void findMiddleNode() {
    Node n1 = headNode;
    Node n2 = headNode;
    while(n2.getNext() != null && n2.getNext().getNext()!= null) {
        n1 = n1.getNext();
        n2 = n2.getNext().getNext();
    }

    System.out.println("middle node is "+n1.getKey());
}

Upvotes: 16

radheshyam
radheshyam

Reputation: 1

import java.util.LinkedList;
import java.util.List;


public class consoleApp 
{
    public static void main(String[] args)
    {
        List list = new LinkedList();
        for (int i = 0; i < 50; i++) 
        {
            list.add(String.valueOf(i));
        }

        int end = list.size();

        int start = 0;
        while (start< end) 
        {
            start++;
            end--;
        }

        if(start == end) 
            System.out.println(start);
    }
}

Upvotes: 0

Andy Khatter
Andy Khatter

Reputation: 165

List list = new LinkedList();
    for (int i = 0; i < 50; i++) {
    list.add(String.valueOf(i));
}

int end = list.size() - 1;
int start = 0;
while (start > end) {
    start++;
    end--;
}
if(start == end) //The arrays length is an odd number and you found the middle
    return start;
else //The arrays length is an even number and there really isn't a middle
    //Do something else here because you have an even number

I saw this code on some other solution page... Is this not another method where the list is being singly traversed!?

Upvotes: 0

Matthew Cox
Matthew Cox

Reputation: 13672

Yes, you can if you are controlling all aspects of the list's adds and deletes.

If you maintain a reference to what is considered to be the midway node during add or deletes then it can be done. There are couple cases that have to be handled. In addition, there are scenarios such as where there is an even number of elements to consider. What will be the midway node in such a situation? ect.. ect..

So you really aren't finding the midway node, but rather, tracking it.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

No, it's not possible. The addresses of the nodes are arbitrary, so there's no way of knowing them without traversing them.

Upvotes: 16

Related Questions