C++ program to print form middle of linked list

Hi there. Today we will see how to print the middle-most element of linked list in C++. There are multiple methods to solve this problem. You can count the number of elements by parsing the list once and get its length, then parsing it again until the half-length. But this method is time-consuming. We will implement this question in a different approach.

We will keep two counters. The 1st one will parse one element at a time. And the 2nd one will parse two elements. When the 2nd pointer reaches the end, it will imply that the 1st one has reached the middle. So we will print the element at the 1st pointer’s node. This approach takes lesser time, because we traverse the list only once. Now, let’s look at the program implementation.

Print form middle of linked list in C++

There will be a separate function for getting the middle element. We will take input in the main method. It will consist of the total number of elements in the linked list, and then their values separated by space. Now, let’s look at the code.

#include<bits/stdc++.h>  
using namespace std;  

struct Node{
  int data;
  struct Node *next;
  Node(int x){
    data=x;
    next=NULL;
  }
};
    
void append(struct Node** head_ref,struct Node** tail_ref,int new_data)
{
  struct Node* new_node =new Node(new_data);
  if(*head_ref==NULL)
    *head_ref=new_node;
  else
    (*tail_ref)->next=new_node;
  *tail_ref=new_node;
}  

void Middle_element(struct Node *head)  
{  
    struct Node *slow_ptr = head;  
    struct Node *fast_ptr = head;  
  
    if (head!=NULL)  
    {  
        while (fast_ptr != NULL && fast_ptr->next != NULL)  
        {  
            fast_ptr = fast_ptr->next->next;  
            slow_ptr = slow_ptr->next;  
        }  
        cout<<endl<<"The middle element is: "<<slow_ptr->data;  
    }  
}
    
int main()  
{    
    struct Node* head = NULL,*tail=NULL;  
    cout<<"Enter the number of elements"<<endl;
    int n,temp;
    cin>>n;
    cout<<"Enter each element separated by space"<<endl;
    for(int i=1;i<=n;i++)
    {
    	cin>>temp;
    	append(&head,&tail,temp);
    }
  	Middle_element(head);
    return 0;  
}

Now let’s look at the output. We will take two test cases.

Test case 1:

Enter the number of elements
12
Enter each element separated by space
1 2 3 4 5 6 7 8 9 10 11 12

The middle element is: 7

Test case 2:

Enter the number of elements
7
Enter each element separated by space
11 12 13 14 15 16 17

The middle element is: 14

Also read: Delete the middle element of a stack in C++

Leave a Reply

Your email address will not be published. Required fields are marked *