Home » Interview Questions » LinkedList Interview Questions » Find middle of the Linked List

Find middle of the Linked List


()

Given a Linked List, write a program to find middle of the linked list

Example

Input : 6->16->15->50->1->23->49

Output : 50

Input : 6->16->15->50->1->23

Output : 50

This is one of the method to find the middle of the Linked List

Time Complexity : O(n)

Algorithm

Tortoise Algorithm
1. Create two pointers slow and fast, initialize them to the head
2. Till fast and fast->next not equal to the null
3. Move the slow pointer one step and move the fast pointer two steps along the linked list
4. return the slow pointer element, which is the middle element

C++ Program

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

struct LL{
	int data;
	LL *next;	
};


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

int middleOfList(struct LL**head)
{
	
	struct LL*slow=*head,*fast=*head;
	while(fast&&fast->next) //if fast not NULL and fast's next is not NULL because it takes two steps
		{
			slow=slow->next; //move this with speed x
			fast=fast->next->next; //move this with speed 2x
		}
	return  slow->data; //middle of list
	//O(number of nodes)
}


void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	//insertAtBeginning(&head,49);
	
	display(&head);
	
	cout<<"Middle of List is "<<middleOfList(&head)<<endl;
	
	return 0;
}

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions