Jul 112012
 

Write a function which will accept a pointer to the head of the linked list and returns a pointer to the middle node of the list. If the list given is

2 -> 3 -> 5 -> 1 -> 4 -> 8 -> 10

Then the function should return a pointer to Node with value 1. If the list has even number of elements

2 -> 3 -> 5 -> 1 -> 4 -> 8

Then you may return a pointer to either 5 or 1 (Since there is no clear middle node).

Another way to ask this question is “Given a linked list, write code to split is in two halves“. In this case also you have to write code to reach to the middle of the list and then update the pointers of the middle node .

Solution:

Simple way (Using 2 loops)

1. Traverse the list to count the total number of nodes in the list 
    Node * temp = head;
    while(temp != NULL){
        temp = temp->link;
        count++;
    }
2. Traverse 'count/2' times forward and return address of the node.
    for(int i=0; i<count/2; i++)
        head = head->next;
    return head;

Using only one loop.

Refer to this post for the Idea. The idea is to take 2 pointer and move one pointer forward at twice the speed of 2nd pointer. When the first reach end of the list, second pointer will be at the middle.

Take 2 pointers, both pointing to the head of the list initially.
While 1st pointer is not NULL
   Move 1st pointer to next of next Node.
   Move 2nd pointer to next Node.
return 2nd pointer

Though this method is not more efficient than the previous one (both in terms of time & memory usage). But sometimes interviewer asks that he want to use only one loop.

    /** 
     *  Function to return the middle element in the list.
     *  Returns NULL, if the list is empty.
     *  Returns the 1st of the 2 middle elements if list has even number of node.
     **/
    Node* getMiddle(Node *head)
    {
        if(head == NULL || head->next == NULL)
            return head;

        Node *ptr1 = head;  // Will move 1 node frwd
        Node *ptr2 = head;  // Will move 2 nodes frwd

        // we don't need to check for ptr1. because ptr2 ahead of ptr1
        while(ptr2->next!= NULL && ptr2->next->next != NULL)
        {
            ptr2 = ptr2->next->next;
            ptr1 = ptr1->next;
        }
        return ptr1;
    }

  One Response to “Finding middle element of Linked list using one loop”

Comments (1)

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)