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;
}

Translate ยป