How to Find a middle element in a link list without traversing the entire list?
I don't see how you could do it without traversing the entire list unless you know the length.
I'm guessing the answer wants one pointer to be traversing one element at a time, while the second pointer moves 2 elements at a time.
This way when the second pointer reaches the end, the first pointer will be at the middle.
The below code will help you get the middle element. You need to use two pointers "fast" and "slow". At every step the fast pointer will increment by two and slower will increment by one. When the list will end the slow pointer will be at the middle.
Let us consider the Node
looks like this
class Node
{
int data;
Node next;
}
And LinkedList has a getter method to provide the head of the linked list
public Node getHead()
{
return this.head;
}
The below method will get the middle element of the list (Without knowing the size of the list)
public int getMiddleElement(LinkedList l)
{
return getMiddleElement(l.getHead());
}
private int getMiddleElement(Node n)
{
Node slow = n;
Node fast = n;
while(fast!=null && fast.next!=null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow.data;
}
Example:
If the list is 1-2-3-4-5 the middle element is 3
If the list is 1-2-3-4 the middle element is 3