Difficulty: Easy, Asked-In: Microsoft, Amazon, Adobe, Morgan Stanley, Qualcomm
Key takeaway: This is an excellent problem to learn problem-solving using fast and slow pointers in a linked list.
Given a singly linked list, write a program to find the middle node of the linked list. If the number of nodes is even, we need to return the second middle node.
Example 1: 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.
Example 2: Input: 6->5->4->3->2->1, Output: 3
Explanation: 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.
The basic idea is to store each linked list node, in the same order, into an extra array with a size equal to the length of the linked list. Then, we can get the middle node by accessing the middle index of the array.
ListNode findMiddleLinkedList(ListNode head)
{
int length = listLength(head)
ListNode temp[length]
int count = 0
while (head != null)
{
temp[count] = head
count = count + 1
head = head->next
}
return temp[count/2]
}
struct ListNode
{
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
int listLength(ListNode* head)
{
int length = 0;
while (head != NULL)
{
length = length + 1;
head = head->next;
}
return length;
}
ListNode* findMiddleLinkedList(ListNode* head)
{
int length = listLength(head);
ListNode* temp[length];
int count = 0;
while (head != NULL)
{
temp[count] = head;
count = count + 1;
head = head->next;
}
return temp[count / 2];
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def listLength(head):
length = 0
while head:
length = length + 1
head = head.next
return length
def findMiddleLinkedList(head):
length = listLength(head)
temp = [None] * length
count = 0
while head:
temp[count] = head
count = count + 1
head = head.next
return temp[count // 2]
Suppose the length of the linked list is n. So the time complexity is the time complexity of finding the length of the linked list + the time complexity of storing nodes in extra memory = O(n) + O(n) = O(n).
The space complexity is O(n) for storing nodes in an n-size array.
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 is to first traverse the linked list to count the number 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.
ListNode findMiddleLinkedList(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
}
struct ListNode
{
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
ListNode findMiddleLinkedList(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;
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findMiddleLinkedList(head):
count = 0
middle = head
while head:
count = count + 1
head = head.next
i = 0
while i < count//2:
middle = middle.next
i = i + 1
return middle
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.
ListNode findMiddleLinkedList(ListNode head)
{
int count = 0
ListNode middle = head
while (head->next != NULL)
{
if (count % 2 == 0)
middle = middle->next
count = count + 1
head = head->next
}
return middle
}
struct ListNode
{
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
ListNode* findMiddleLinkedList(ListNode* head)
{
int count = 0;
ListNode* middle = head;
while (head->next != NULL)
{
if (count % 2 == 0)
middle = middle->next;
count = count + 1;
head = head->next;
}
return middle;
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findMiddleLinkedList(head):
count = 0
middle = head
while head.next is not None:
if count % 2 == 0:
middle = middle.next
count = count + 1
head = head.next
return middle
We are running a single loop and performing constant operations at each iteration. So the time complexity is O(n). The space complexity is O(1), as we are using constant extra space.
Now, the critical question is: Can we come up with another approach to finding the middle node in a single traversal? Let's think!
Suppose we use two pointers to traverse the linked list, where one pointer is moving with double the speed of the other 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, and we can get the middle node in a single scan of the linked list.
ListNode findMiddleLinkedList(ListNode head)
{
ListNode fast = head
ListNode slow = head
while (fast != * NULL && fast->next != * NULL)
{
slow = slow->next
fast = fast->next->next
}
return slow
}
struct ListNode
{
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
ListNode* findMiddleLinkedList(ListNode* head)
{
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findMiddleLinkedList(head):
fast = head
slow = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}
public class Solution
{
public ListNode findMiddleLinkedList(ListNode head)
{
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
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. The time complexity is n/2 * O(1) = O(n).
The space complexity is O(1), as we are using constant extra space.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.