Find Middle of the Linked List

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

Key takeaway: An excellent problem to learn problem-solving using fast and slow pointers.

Let’s understand the problem!

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 3.

Discussed solution approaches

• Brute force approach  using extra memory
• By counting nodes: Double traversal
• By counting nodes: Single traversal
• Efficient solution  using slow and fast pointers

Brute force approach  using extra memory

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.

Implementation code C++

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];
}

Implementation code Python

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]

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 the linked list + 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.

By counting nodes: Double traversal

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 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.

Solution steps

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

Implementation code C++

ListNode findMiddleLinkedList(ListNode* head)
{
    int count = 0;
    ListNode middle = *head;

    // Count the number of nodes in the linked list
    while (head != NULL)
    {
        count = count + 1;
        head = head->next;
    }

    // Find the middle node
    int i = 0;
    while (i < count / 2)
    {
        middle = *(middle.next);
        i = i + 1;
    }

    return middle;
}

Implementation code Java

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;
}

Implementation code Python

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

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.

By counting nodes: single traversal

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 until head->next is not equal to NULL. At each iteration, we increment the count value by 1. When the count value is even, we increment the middle pointer by one.
• By the end of the loop, the middle pointer will be at the middle node.

Implementation code C++

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;
}

Implementation code Python

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

Implementation code Java

ListNode findMiddle(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;
}

Time and space complexity analysis

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.

Efficient solution using slow and fast pointers

Solution idea

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.

Solution steps

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

Implementation code C++

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;
}

Implementation code Python

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

Implementation code Java

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;
}

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 O(1) operation at each iteration. Time complexity = n/2 * O(1) = O(n). The space complexity is O(1), as we are using constant extra space.

Comparison of time and space complexities

• 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).

Critical ideas to think!

1. Can the above approaches work if the linked list has a loop?
2. In terms of pointer movement, which approach seems more efficient?
3. How do we modify the above code to delete the middle node?
4. In the case of an even nodes, how do we modify the above code to return the first middle node?
5. In the case of the fast and slow pointers approach, can we optimize it further by using the head as the slow pointer? If yes, then how do we modify the above code?
6. Can this problem be solved using other approaches?

Suggested coding questions to practice

• Reversing a linked list
• Remove the Nth node from the list end
• Detect loop in a linked list
• Swap list nodes in pairs
• Merge two sorted list
• Reverse a linked list in groups of a given size
• Intersection points in Y shaped linked lists

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!