How to Find the middle element of a linked list without traversing twice ?
Linked list is singly linked list(there is only next pointer no previous pointer).
See Solution: Find middle element of a linked list
Take two pointers both pointing to head of the linked list( pointer1 and pointer2 ). Now increment pointer1 by one node and pointer2 by two nodes at a time in a while loop till pointer 2 reaches end of the list or becomes null, at this point the node which pointer1 is pointing to will be the middle element/node of the linked list.
Code in C/C++
Node* getMiddleElement(Node * node){ Node* pointer1 = node; Node* pointer2 = node; //traverse till pointer2 reaches end of the list or becomes null while(pointer2 != null && pointer2->next != null){ pointer1 = pointer1->next; pointer2 = pointer2->next->next; } return pointer1; }
Facebook Comments
Rohit5 says
Cool. By the way if you want to do it in Java than here is a sample program to find middle element of LinkedList in Java