Finding middle element in a linked list

Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.

Example 1:

Input:
LinkedList: 1->2->3->4->5
Output: 3 
Explanation: 
Middle of linked list is 3.

Example 2: 

Input:
LinkedList: 2->4->6->7->5->1
Output: 7 
Explanation: 
Middle of linked list is 7.


method 1:

first find the number of elements in linked list

than traverse again to find the middle element.

c++ implementation:

int getMiddle(Node *head)

{

    Node*t=head; int c=1;

    //this below loop to find the no. of elements in linked list

    while (t->next!=NULL)

    {

        t=t->next;

        c++;

    }

    

    t=head;

    

    //this below loop to find the middle element

    for(int i=0;i<(c/2);i++)

    {

         t=t->next;

    }

    return t->data;

    

}

Time Complexity: O(n+n/2) ≈ 0(n)
space complexity:0(1)



method 2:

Find middle element using two pointer technique. Take two pointers i.e. fast and slow. Start both pointers from head. Fast pointer will move double the slow pointer each time till it reaches end. As soon as fast pointer reaches end , our slow pointer will be on the middle element.

c++ implementation:

int getMiddle(Node *head)

{

    if(head==NULL )

    return -1;


     Node*s=head;

     Node*f=head;

   while( f!=NULL && f->next!=NULL)

   {

       s=s->next;

       f=f->next->next;

   }

   

   return s->data;

    

}

Time Complexity: O(n/2)  
space complexity:0(1)


darkmode