**Difficulty:** Easy, **Asked-In:** Microsoft, Amazon, Adobe, Morgan Stanley, Qualcomm

**Key takeaway:** An excellent problem to learn problem-solving using fast and slow pointers in the linked list.

Given a singly linked list, write a program to find the middle node of the linked list. If the node count is even then we need to return the second middle node.

**Examples**

Input: 5->4->**3**->2->1, Output: 3

Explanation: Here the number of nodes is 5, so there is one middle node which is 3.

Input: 6->5->4->**3**->2->1, Output: 3

Explanation: Here the number of nodes is 6, where the first middle node is 4 and the second middle node is 3. So we need to return the pointer to the node value 3.

- A brute force approach using extra memory
- By counting nodes: double traversal of the linked list
- By counting nodes: single traversal of the linked list
- An efficient solution using slow and fast pointers

The basic idea would be to store each linked list node (in the same order) into an extra array size equal to the length of the linked list and get the middle node by accessing the middle index of the array.

**Solution Pseudocode**

```
ListNode getMiddleNode(ListNode head)
{
int length = listLength(head)
ListNode temp[length]
int count = 0
while (head->next != null)
{
temp[count] = head
count = count + 1
head = head->next
}
return temp[count/2]
}
```

**Time and space complexity analysis**

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the length of linked list + Time complexity of storing nodes into extra memory = O(n) + O(n) = O(n)

Space complexity = O(n), for storing nodes into n size array.

**Solution Idea**

In the above approach, we are using extra space to find the middle node of the linked list. Now the critical question is: can we reduce the space complexity to O(1)?

One idea would be to first traverse the linked list to count no. of nodes and then traverse the list again count/2 number of times. So by the end of the second traversal, we will be present at the middle node.

**Solution Steps**

- We initialize the variable
**count**equal to 0. - We also initialize a list pointer
**middle**to track the middle node i.e. middle = head. - Now we run a loop till
**head!= NULL**and count number of nodes. - Now we run another loop till the
**i < n/2**and increment the value of the middle pointer in each iteration. - By end of the second loop, we return the middle pointer.

**Solution Pseudocode**

```
ListNode getMiddleNode(ListNode head)
{
int count = 0
ListNode middle = head
while (head != NULL)
{
count = count + 1
head = head->next
}
int i = 0
while (i < count/2)
{
middle = middle->next
i = i + 1
}
return middle
}
```

**Time and space complexity analysis**

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the node count + Time complexity of finding the middle node = O(n) + O(n) = O(n)

Space complexity = O(1), as we are using constant extra space.

Here is another idea: we can track the count of nodes and the middle node simultaneously in a single traversal.

- We initialize a variable
**count**to track the node count. - Also, we initialize a pointer
**middle**to track the middle node. - Now we run a loop till head != NULL.
- At each iteration, we increment the count value by 1. When the count value will be even, we increment the middle pointer by one.
- By the end of the loop, the middle pointer will be at the middle node, and we return this value.

**Solution Pseudocode**

```
ListNode getMiddleNode(ListNode head)
{
int count = 0
ListNode middle = head
while (head != NULL)
{
if (count % 2 == 0)
middle = middle->next
count = count + 1
head = head->next
}
return middle
}
```

**Time and space complexity analysis**

We are running a single loop and doing constant operations at each iteration. So time complexity = O(n). Space complexity = O(1), as we are using constant extra space.

**Solution Idea**

Now the critical question is: can we come up with some other approach to find the middle node in a single traversal? Let's think!

Suppose we take two-pointers to traverse the linked-list, where one pointer is moving with double the speed of another pointer. So when the **fast** pointer reaches the end of the linked list then the **slow** pointer must be present at the middle node. The idea looks straightforward where we can get the middle node in a single scan of the linked list.

**Solution Steps**

- We initialize
**slow**(always move by one step) and**fast**(always move by two-step) pointers with the head node. - Now run a loop until
**fast**or**fast->next**becomes NULL. - At each iteration of the loop, we move the slow pointer by 1 and the fast pointer by 2 steps forward.
- By end of the loop, the slow pointer will point to the middle node and we return it.

**Solution Pseudocode**

```
ListNode getMiddleNode(ListNode head)
{
ListNode fast = head
ListNode slow = head
while (fast != null && fast->next != null)
{
slow = slow->next
fast = fast->next->next
}
return slow
}
```

**Time and space complexity analysis**

If the number of nodes is n then the fast pointer will move n/2 steps to reach the end. Similarly, the slow pointer will also move n/2 steps to reach the middle node. So we are running a single loop n/2 number of times and doing an O(1) operation at each iteration. Time complexity = n/2 * O(1) = O(n)

Space complexity = O(1), as we are using constant extra space.

- Using extra memory: Time = O(n), Space = O(n)
- By counting nodes (Double traversal): Time = O(n), Space = O(1)
- By counting nodes (Single traversal): Time = O(n), Space = O(1)
- Using slow and fast pointers: Time = O(n), Space = O(1)

- Can the above approaches work if the linked link has a loop?
- In terms of pointer movement, which approach looks more efficient? Compare the number of operation count for each approach?
- How do we modify the above code to delete the middle node?
- In the case of an even number of nodes, how do we modify the above code to return the first middle node?
- In the case of the fast and slow pointers approach, can we optimize it further use the head as the slow pointer? If yes, then how do we modify the above code?
- Can we solve this problem using some other approaches?

- Reversing a Linked List
- Remove Nth Node from List End
- Detect Loop in a Linked Lis
- Swap List Nodes in pairs
- Merge two sorted list
- Reverse a Linked List in groups of a given size
- Intersection Point in Y Shaped Linked Lists

Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.