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
Solution
- Naive approach
- Optimized approach using fast and slow pointers

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 \leq$ n $\leq 100$
$1 \leq$ node.data $\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 $\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)$ , where $n$ 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 to solve this problem with constant space complexity. The slow pointer traverses the linked list one step at a time, while the fast pointer takes two steps at a time. This makes the fast pointer reach the end of the linked list in $\frac{n}{2}$ iterations, and the slow pointer, by this time, reaches the middle of the linked list.

The following steps are applied when identifying the middle of the linked list:

Create two pointers, slow and fast, initially at the head of the linked list, that is, pointing to the first node.
Traverse the linked list using both pointers, where the slow pointer will move one step forward, and the fast pointer will move two steps forward.
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.

main.py

linked_list_node.py

linked_list.py

print_list.py

from linked_list import LinkedList
from print_list import print_list_with_forward_arrow
def get_middle_node(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
# Driver code
def main():
    input = (
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5, 6],
        [3, 2, 1],
        [10],
        [1, 2],
    )
    for i in range(len(input)):
        input_linked_list = LinkedList()
        input_linked_list.create_linked_list(input[i])
        print(i+1, ".\tLinked list: ", sep="", end="")
        print_list_with_forward_arrow(input_linked_list.head)
        print("\n\tMiddle of the linked list: ",
              get_middle_node(input_linked_list.head).data)

Enter to Rename, Shift+Enter to Preview

Middle of the Linked List

Solution summary#

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

Create two pointers, slow and fast, initially at the head of the linked list.
While traversing the linked list, move the slow pointer one step forward and the fast pointer two steps forward.
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)$ , where $n$ is the number of nodes in the linked list.

Space complexity#

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

Middle of the Linked List

Modified Binary Search: Introduction