Write a program to print middle element of a linked list. It is also the most asked question in interviews. I assume you have a basic understanding of linked list and it’s concept.
First Method:
i) Traverse a linked list and maintain the count of nodes.
ii) After traversing a linked list we know it’s length. In a second traversal, traverse the linked list by count/2 and print the last element(count/2). We get the middle element of a linked list.
The above method works good. But you can solve this problem in one pass, by using two pointers.
Program to Reverse a Linked List
Second Method:
i) Take two pointers. Move the first pointer by one and second pointer by two.
ii) When the second pointer reaches at the end of a linked list. The first pointer points to the middle element of a linked list.
Program to Print Middle Element of a Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <stdio.h> struct node{ int data; struct node* next; }; struct node* head; void insert_node(int data){ /* Creating a new node */ struct node* newnode=(struct node*)malloc(sizeof(struct node*)); newnode->data = data; newnode->next = head; head = newnode; } void middleelement(){ /* Take two pointers first and second */ struct node *first,*second; first=second = head; if(head!=NULL){ while(second!=NULL && second->next!=NULL){ /* Move first by one and second by two step */ second = second->next->next; first=first->next; } /* Print value of first node which points to middle */ printf("Middle element is %d",first->data); } } main() { head = NULL; insert_node(2); insert_node(4); insert_node(6); insert_node(8); insert_node(9); middleelement(); } |
