### Intoduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we are given a linked list. We have to find the middle of the linked list.

### Problem Statement Understanding

Let's suppose we have a linked list whose length is **L**, then the middle of the linked list will be the **(L/2)**^{th} node of the linked list.

Suppose the given list is 5 â†’ 10 â†’ 3 â†’ 4 â†’ 8.

- The length of this linked list is 5.
- So, (5/2) = 2
^{nd}node will be the middle node of the linked list. - The middle of the linked list will be the node at 2
^{nd}position, which is 3, considering 0 based indexing.

Taking another example, letâ€™s assume that the given linked list 1 â†’ 3 â†’ 5 â†’ 7 â†’ 9 â†’ 11.

- In this case, the length of this linked list is 6. So, (6/2) = 3
^{rd}node will be the middle node of the linked list. - The middle of the linked list will be the node at 3
^{rd}position, which is 7, considering 0 based indexing.

Now, I think from the above examples, the problem statement is clear. Letâ€™s see how we can approach it.

Before moving to the further to approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

There are two solutions to this problem. One is the naive one and the second one is the optimal solution. The naive solution requires two traversals of the list, while the optimal solution only requires a single traversal of the linked list.

Let's have a glance at the naive approach and then see what we can do to optimize it.

### Approach and Algorithm (Naive approach)

Here, in this approach, we first calculate the length of the list. Let the length be **len**.

- Now, we traverse till the
**(len/2)**^{th}node and print it as it is obviously the middle node of the list.

This is the naive approach to solve this problem, but as we are preparing for coding interviews of big companies, we should be familiar with technique to find the middle node of the linked list without finding the length first.

The optimal solution requires a single traversal of the linked list and is the best way to find the middle of a linked list.

**Time Complexity:** O(N) - two traversals required.

**Space Complexity:** O(1), as only temporary variables are being created.

**Now, let us discuss the approach in which we can find the middle of a linked list with a single traversal**.

What if we start by taking two pointers, say **slow** and **fast**, and make both of them point to the **head** initially.

- Now, what will happen if we make the
**slow**jump one place and the**fast**jump two places (**fast moving with twice the speed of slow**). - If we notice carefully, by doing the above step, when the
**fast**will reach the end of the list, the**slow**will be pointing to the**middle**of the list. With the help of this technique, we can reach the**middle node of a linked list in a single pass**.

**Note:** The reason why our **slow** pointer will be pointing to the **middle** of the linked list when the **fast** pointer is at the end is that, as our **slow** pointer is travelling with half the speed of **fast** pointer so when the **fast** pointer will reach the end of the linked list, till that time **slow pointer will have only travelled half the distance as travelled by fast pointer** and hence it will be at the **middle of the linked list**.

Do you know what the above-explained method is called?

- This method is called the
**tortoise and hare method**or the**slow and fast pointer method**. The slow and fast pointer method has been explained in detail in the approach section and the dry run.

Let us have a glance at the approach.

### Approach (Optimal)

Let us see what the **slow and fast pointer technique** is:

- Initially, both the pointers will point to the
**head**of the linked list. - Then, we will move both of the pointers.
- The
**fast pointer**will jump**two places**, whereas the**slow pointer**will**one place**.

- The
- When the
**fast pointer**will reach the end of the linked list, the**slow pointer**will be pointing to the**middle of the linked list**.

### Algorithm

- Create two pointers say
**slow**and**fast**. Initially, point both the**slow**and the**fast**to the head of the list. - Now, the
**slow**will jump one place, and the**fast**will jump two places until the**fast**reaches the end of the list. - When the
**fast pointer reaches the end**of the list, the**slow will be pointing to the middle**of the list. - In the end, return the data of the
**slow pointer**, as the slow will be pointing to the middle of the list.

### Dry Run

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_1-5.png)

### Code Implementation

#include#include // Node structure of a linked list node struct Node { int data; struct Node* next; }; // Using this function we will find and print the middle of the linked list void findMiddle(struct Node *head) { struct Node *slow_ptr = head; struct Node *fast_ptr = head; if (head!=NULL) { while (fast_ptr != NULL && fast_ptr->next != NULL) { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } printf("The middle element is %d\n\n", slow_ptr->data); } } // Using this function we will create a new node and will insert at the beginning of the list void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Using this function we will print the linked list void printList(struct Node *ptr) { while (ptr != NULL) { printf("%d->", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // Driver Function int main() { struct Node* head = NULL; int i; push(&head,8); push(&head,4); push(&head,15); push(&head,10); push(&head,5); printf("The Linked List is : "); printList(head); findMiddle(head); return 0; }

#### Output:

The Linked List is : 5->10->15->4->8->NULL

The middle element is 15

**Time Complexity:** O(n), a single list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to find the middle of a linked list. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.