**Problem Statement: **Given the** head** of a singly linked list, return *the middle node of the linked list*. If there are two middle nodes, return the second middle node.

**Examples**:

Input Format: ( Pointer / Access to theheadof a Linked list ) head = [1,2,3,4,5]Result: [3,4,5] ( As we will return the middle of Linked list the further linked list will be still available )Explanation: The middle node of the list is node 3 as in the below image.

Input Format:Input: head = [1,2,3,4,5,6]Result: [4,5,6]Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: **Naive Approach

**Intuition: **We can traverse through the Linked List while maintaining a count of nodes let’s say in variable **n**, and then traversing for 2nd time for** n/2** nodes to get to the middle of the list.

**Code**:

## C++ Code

```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int n = 0;
ListNode* temp = head;
while(temp) {
n++;
temp = temp->next;
}
temp = head;
for(int i = 0; i < n / 2; i++) {
temp = temp->next;
}
return temp;
}
};
```

## Python Code

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
n = 0
temp = head
while temp:
n += 1
temp = temp.next
temp = head
for i in range(n // 2):
temp = temp.next
return temp
```

**Solution 2**: [Efficient] Tortoise-Hare-Approach

Unlike the above approach, we don’t have to maintain node count here and we will be able to find the middle node in a single traversal so this approach is more efficient.

**Intuition: **In the Tortoise-Hare approach, we increment slow ptr by 1 and fast ptr by 2, so if take a close look fast ptr will travel double that of the slow pointer. So when the fast ptr will be at the end of the Linked List, slow ptr would have covered half of the Linked List till then. So slow ptr will be pointing towards the middle of Linked List.

**Approach: **

- Create two pointers slow and fast and initialize them to a head pointer.
- Move slow ptr by one step and simultaneously fast ptr by two steps until fast ptr is NULL or next of fast ptr is NULL.
- When the above condition is met, we can see that the slow ptr is pointing towards the middle of the Linked List and hence we can return the slow pointer.

**Code**:

## C++ Code

```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next)
slow = slow->next, fast = fast->next->next;
return slow;
}
};
```

## Java Code

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
```

## Python Code

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
```

**Time Complexity: **O(N)

**Space Complexity: **O(1)

**Follow-up question you can try: **Detect and remove Loop in Linked List

Special thanks to

Aditya Shahareandfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article.Sudip Ghosh