Middle element of a Linked List

Today we will be discussing the algorithm to print middle element of a linked list. If you are new to linked list data structure then please refer to this link where I have explained everything about linked list. Suppose you have a list like 1->4->2->8->5 then the middle element of this list will be 2. SO we will write a program which will do so but first let's discuss the procedure.

Procedure

1. First we will make a linked list.
2. Then we will count the number of nodes in this list.

• A list which will have even number of nodes will have 2 middle nodes at position 'n/2' and 'n/2+1' (n is number of nodes in a list).
• A list which will have odd number of nodes will have 1 middle element only at position (n+1)/2 (n is number of nodes in a list).

3. Then depending on even or odd number of nodes we will iterate the list till the positions mentioned above and print the values.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next =temp; } } void middle() { struct node* temp=head; int c=0; int mid1; int p=1; while(temp!=NULL) { temp=temp->next; c++; } temp=head; if(c%2==0) { mid1=c/2; while(temp!=NULL) { if(p==mid1) break; p++; temp=temp->next; } cout<<"Middle values are "<<temp->data<<"and"<<temp->next->data<<endl; } else if(c%2!=0) { mid1=(c+1)/2; while(temp!=NULL) { if(p==mid1) break; p++; temp=temp->next; } cout<<"Middle values are "<<temp->data<<endl; } } void disp() { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(2); l.insert(5); l.insert(21); l.insert(46); l.insert(48); l.insert(54); l.insert(10); l.insert(6); l.insert(18); l.insert(-4); l.disp(); l.middle(); return 0; }

Explanation of Code 

1. First we will write a simple code of linked list which will have 2 functions:

     - insert() - which will insert elements in the linked list.
     - disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we have created a function named middle() which will print the middle element of a linked list.
4. First we have created a 'temp' which is pointer to node. Then we have created some other variables like 'c=0', 'mid1', 'p=1'.
5. Then we have started a while loop to count number of nodes in the list. The number of nodes are stored in variable 'c'.
6. Then we have initialized temp to head.
7. Then there is an if condition which checks if c%2==0 or not i.e number of nodes in the list are even or not.
8. If the number of nodes in the list are even then we have stored the middle value c/2 in a variable mid1.
9. Then we have started a while loop which will iterate till 'mid1' in the list. If 'p' is equal to 'mid1' then we will break out of the loop because we have reached the middle of the list. Otherwise we will increment p and temp.
     while(temp!=NULL)
     {
          if(p==mid1)
                break;
          p++;
          temp=temp->next;
     }
10. Then we have printed the middle values. First we have printed temp->data which will display the first middle node the we have printed the second middle value by using temp->next->data which will point to the data part of the next of the first middle value.
11. If the number of nodes in the list are not even the they will be odd. So the next if condition where we have checked if c%2!=0 is for odd number of nodes.
12.  If the number of nodes in the list are odd then we have stored the middle value (c+1)/2 in a variable mid1.
13. Then we have started a while loop which will iterate till 'mid1' in the list. If 'p' is equal to 'mid1' then we will break out of the loop because we have reached the middle of the list. Otherwise we will increment p and temp.
      while(temp!=NULL)
      {
             if(p==mid1)
                    break;
             p++;
             temp=temp->next;
      }
14. Then we have simply printed the value at mid1 by using temp->data which is the middle element.