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

Try It

**Next >**
**< Prev**