Please enable JavaScript to view this page content properly.

Linked List: Find the middle element

Please enable JavaScript to view this page content properly.

Question: Given a singly linked list, find the node in the middle.

Please enable JavaScript to view this page content properly.

Solution 1: Walk the linked list to find the length of the list. Lets say n is the length of the list. Walk the list again upto âŒŠ n/2 âŒ‹.

Solution 2: Use two pointers.
Move one pointer at twice the speed of the second. When the 1st pointer
reaches the end of the list, the 2nd pointer will be pointing to the
middle node.
Note: If the list has even number of nodes, the middle node will be floor of âŒŠ n/2 âŒ‹.

Code:

Node * FindMiddle(Node *listHead) { Node *ptr1, *ptr2; // we need 2 pointers ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

int i=0;

while(ptr1->next != NULL) // keep looping until we reach the tail // (next will be NULL for the last node) { if(i == 0) { ptr1 = ptr1->next; //increment only the 1st pointer i=1; } else if( i == 1) { ptr1 = ptr1->next; //increment both pointers ptr2 = ptr2->next; i = 0; } } return ptr2; //now return the ptr2 which points to the middle node }