Solution: Middle of the Linked List

Let's solve the Middle of the Linked List problem using the Fast and Slow Pointers pattern.

We'll cover the following

Statement

Given the head of a singly linked list, return the middle node of the linked list. If the number of nodes in the linked list is even, there will be two middle nodes, so return the second one.

Constraints:

Let n be the number of nodes in a linked list.

  • 1≤1 \leq n ≤100\leq 100
  • 1≤1 \leq node.data ≤100\leq 100
  • head ≠\neq NULL

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

In the naive approach, we use an external array to store the elements of the linked list, and then we return the element present at the index ⌊array.length2⌋\lfloor \frac{array.length}{2} \rfloor as the middle node of the linked list. The time and space complexity of this approach is O(n)O(n), where nn is the number of nodes in the linked list. Let’s see if we can solve this problem with better time and space complexity.

Optimized approach using fast and slow pointers

We can use the fast and slow pointers technique to efficiently find the midpoint of the list by just leveraging the relative speeds of the pointers—one moving at a slower pace than the other. Both pointers initially point to the head of the linked list. As the pointers traverse the list, the slow pointer advances one node at a time while the fast pointer moves two nodes at a time. This ensures that when the fast pointer reaches the last node of the linked list (for the odd-numbered list) or NULL (for the even-numbered list), it has traversed twice the number of nodes as the slow pointer. Consequently, for odd-numbered lists, the slow pointer will be positioned precisely at the middle node, while for even-numbered lists, it will be positioned at the second node out of the two middle nodes. This approach minimizes space complexity and completes the task in a single pass through the linked list.

Let's go over the workflow of the algorithm:

  1. Initialize two pointers, slow and fast, at the head of the linked list, slow = head and fast = head.

  2. Traverse the linked list by moving the slow pointer one step forward, slow = slow.next, and the fast pointer two steps forward, fast = fast.next.next.

  3. When the fast pointer reaches the last element of the linked list, or becomes equal to NULL, the slow pointer, at that time, will point to the middle node. Return the node that the slow pointer points to.

The slides below help to understand the solution in a better way.

Press + to interact
canvasAnimation-image
1 of 6

Let’s look at the code for this solution below:

main.java
LinkedListNode.java
LinkedList.java
PrintList.java
class MiddleNode {
    public static LinkedListNode middleNode(LinkedListNode head) {
        LinkedListNode slow = head;
        LinkedListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;	
            fast = fast.next.next; 
        }
        return slow;
    }
    // Driver code
    public static void main( String args[] ) {
        
        int[][] input = {{1, 2, 3, 4, 5}, {1, 2, 3, 4, 5, 6}, {3, 2, 1}, {10}, {1, 2}};
        
          for(int i=0; i<input.length; i++){
            System.out.print(i+1);
            LinkedList<Integer> list = new LinkedList<Integer>();
            list.createLinkedList(input[i]);
            System.out.print(".\tInput linked list:  ");
            PrintList.printListWithForwardArrow(list.head);
            System.out.print("\tMiddle of the linked list is:  " );
            System.out.println(middleNode(list.head).data);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Middle of the Linked List

Solution summary

To recap, the solution to this problem can be divided into the following steps:

  1. Create two pointers, slow and fast, initially at the head of the linked list.
  2. While traversing the linked list, move the slow pointer one step forward and the fast pointer two steps forward.
  3. When the fast pointer reaches the last node or NULL, the slow pointer will point to the middle node of the linked list. Return the node that the slow pointer points to.

Time complexity

The time complexity of the solution above is O(n)O(n), where nn is the number of nodes in the linked list.

Space complexity

The space complexity of this solution is constant, that is, O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.