.png)
Middle of a Linked List
Problem Statement
Given a singly linked list, find and return the middle node of the linked list.
Rules
- If the number of nodes is odd, return the exact middle node.
- If the number of nodes is even, return the second middle node (this is the standard convention followed in most interviews and coding platforms).
Understanding the Problem
Example 1 (Odd Length)
Input:
1 → 2 → 3 → 4 → 5 → NULL
Output:
3
Example 2 (Even Length)
Input:
10 → 20 → 30 → 40 → NULL
Output:
30
Explanation:
There are two middle nodes (20 and 30). We return the second middle node.
Important Edge Cases
- Empty linked list → no middle node
- Linked list with one node → that node is the middle
- Linked list with two nodes → return the second node
Handling edge cases is crucial in interviews.
Approach 1: Two-Pointer Technique (Slow and Fast Pointer)
Core Idea (Most Important)
This is the optimal and most widely accepted approach.
- Use two pointers:
- slow moves one step at a time
- fast moves two steps at a time
- When fast reaches the end:
- slow will be at the middle
Why This Works
- Fast pointer travels twice as fast
- When fast finishes the list, slow has covered half the distance
Algorithm
- Initialize two pointers slow and fast to head
- While fast and fast.next are not NULL:
- Move slow by one node
- Move fast by two nodes
- Return slow
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Implementation (All Languages)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
/* Function to find middle using slow-fast pointers */
struct Node* findMiddle(struct Node* head) {
if (head == NULL)
return NULL;
struct Node* slow = head;
struct Node* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow; // second middle in even case
}
/* Helper to insert node at end */
struct Node* insert(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
/* Driver Code */
int main() {
struct Node* head = NULL;
// Example: 10 → 20 → 30 → 40
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 30);
head = insert(head, 40);
struct Node* mid = findMiddle(head);
if (mid != NULL)
printf("Middle Node: %d\n", mid->data);
else
printf("List is empty\n");
return 0;
}Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MiddleOfLinkedList {
public static Node findMiddle(Node head) {
if (head == null)
return null;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def find_middle(head):
if head is None:
return None
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Dry Run (Very Important for Students)
Input
1 → 2 → 3 → 4 → 5 → NULL
Pointer Movement
| Step | Slow | Fast |
|---|---|---|
| Start | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| Stop | 3 | NULL |
Result
Middle node = 3
Approach 2: Counting Nodes (Brute Force Method)
This approach finds the middle of the linked list by counting the total number of nodes first, and then traversing the list again to reach the middle position.
Although this method is less efficient than the two-pointer technique, it is very useful for beginners and helps build a strong understanding of linked list traversal.
Algorithm
- If the linked list is empty, return NULL.
- Traverse the list and count the total number of nodes (n).
- Calculate the middle position:
- middle = (n / 2) + 1
- Traverse the list again up to the middle position.
- Return the node at that position.
For even-length lists, this formula returns the second middle node, which matches standard interview conventions.
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
- Traversals Required: 2
Implementation
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
/* Function to find middle by counting nodes */
struct Node* findMiddleByCounting(struct Node* head) {
if (head == NULL)
return NULL;
int count = 0;
struct Node* temp = head;
// First traversal (count nodes)
while (temp != NULL) {
count++;
temp = temp->next;
}
int middle = (count / 2) + 1;
// Second traversal
temp = head;
for (int i = 1; i < middle; i++) {
temp = temp->next;
}
return temp;
}
/* Helper to insert node */
struct Node* insert(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
/* Driver Code */
int main() {
struct Node* head = NULL;
// Example: 10 → 20 → 30 → 40
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 30);
head = insert(head, 40);
struct Node* mid = findMiddleByCounting(head);
if (mid != NULL)
printf("Middle Node: %d\n", mid->data);
else
printf("List is empty\n");
return 0;
}
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MiddleOfLinkedListCount {
public static Node findMiddleByCounting(Node head) {
if (head == null)
return null;
int count = 0;
Node temp = head;
// First traversal
while (temp != null) {
count++;
temp = temp.next;
}
int middle = (count / 2) + 1;
// Second traversal
temp = head;
for (int i = 1; i < middle; i++) {
temp = temp.next;
}
return temp;
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def find_middle_by_counting(head):
if head is None:
return None
count = 0
temp = head
# First traversal to count nodes
while temp:
count += 1
temp = temp.next
middle = (count // 2) + 1
# Second traversal to reach middle
temp = head
for _ in range(1, middle):
temp = temp.next
return temp
Dry Run
Input
10 → 20 → 30 → 40 → NULL
Step 1: Count Nodes
Total nodes = 4
Step 2: Calculate Middle
middle = (4 / 2) + 1 = 3
Step 3: Traverse to Position 3
Node = 30
Comparison of Approaches
| Approach | Time | Space | Traversals |
|---|---|---|---|
| Two Pointer | O(n) | O(1) | 1 |
| Counting | O(n) | O(1) | 2 |
Common Mistakes Students Make
- Returning first middle in even-length list (wrong as per standard)
- Incorrect while condition
- Not checking fast.next
- Forgetting empty list case
- Infinite loop due to pointer misplacement
Interview Perspective
- This problem tests:
- Pointer manipulation
- Loop conditions
- Understanding of linked list traversal
- Interviewers expect the two-pointer approach
- Always explain why slow-fast works
Variations of This Problem
Practice these next:
- Find first middle node
- Find middle of circular linked list
- Print both middle nodes
- Delete middle node
- Find middle in doubly linked list
Summary
- The two-pointer approach is optimal and elegant
- Works in one traversal
- No extra space required
- A foundational problem for advanced linked list questions
Mastering this problem makes solving cycle detection, palindrome check, and reversal problems much easier.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
