Codewhoop

# Display middle element of a linked list

  • Two Pass:

    1. The basic way we can do this is by counting the number of elements in the linked list in one pass, say it comes out to be n.
    2. n/2 will be the middle element and again we would need to traverse till n/2 to get to the middle element and then display it.

  • One Pass:

    1. Create two pointers slow and fast.
    2. Move the fast pointer two nodes at a time & slow pointer one node at a time.
    3. Check when the link part of the fast pointer becomes NULL (odd number of nodes) or the fast pointer becomes NULL (even number of nodes), at that point slow pointer points to the middle element.

# Source Code - C++

#include <iostream>
using namespace std;

//Creating Node Structure
struct Node{
 int data;
 Node *link;
};
//creating head pointer and equating to NULL
Node *head=NULL;

//Function to Display middle element
void showMid()
{
  Node *slow=head;
  Node *fast=head;

  if(head==NULL)
   cout<<"List is Empty";
  else
  {
   while(fast!=NULL && fast->link!=NULL)
   {
    slow=slow->link;
    fast=fast->link->link;
   }
   cout<<"Middle element is:"<<slow->data;
  }

}

//Function to insert at the end of linked list
void insertEnd (int d)
{

 Node *ptr = new Node();
 ptr->data=d;
 ptr->link=NULL;

 if(head==NULL)
 head=ptr;
 else
 {
  Node *temp = head;
  while(temp->link != NULL)
  {
   temp=temp->link;
  }
  temp->link=ptr;

 }

}

//Main Function
int main()
{
 insertEnd(2);
 insertEnd(9);
 insertEnd(1);
 insertEnd(3);
 insertEnd(7);

 showMid();
 return 0;
}

Time Complexity O(n)