LeetCode: Middle of the Linked List — Optimal Solution Explained

LeetCode: Middle of the Linked List — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

We will delve into a common linked list problem: finding the middle of a singly linked list. While there are various ways to approach this problem, we will focus on a particularly efficient and elegant technique known as the tortoise and hare algorithm or the slow and fast pointer method.

We will guide you step by step, using clear visuals to demonstrate how the solution works with time complexity of O(n) and space complexity of O(1)

Intuition/Solution

The intuition behind the tortoise and hare algorithm (slow and fast pointer method) is to use two pointers traversing the linked list at different speeds. The tortoise (slow) pointer moves one step at a time, while the hare (fast) pointer moves two steps at a time. By doing this, when the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.

This is because the fast pointer moves twice as fast and travels twice the distance. In other words, the slow pointer will always travel HALF the distance from the fast pointer. If the fast pointer is at node 5, the slow pointer would be at node 3. If the fast pointer is at node 7, the slow pointer would be at node 4. We can extrapolate this, so that when the fast pointer is at the END of the linked list, the slow pointer would be exactly at the middle node.

Using the intuition above, let’s write down a solution.

1. Initialize two pointers: slow and fast, both pointing to the head of the linked list.
2. Iterate through the list while the fast pointer and its next node are not null: a. Move the slow pointer one step forward (i.e., slow = slow.next). b. Move the fast pointer two steps forward (i.e., fast = fast.next.next).
3. When the loop ends, the slow pointer will be at the middle of the list. Return the slow pointer.

Step-by-Step Visual Guide

Case 1: Odd number of nodes

5 nodes: 1-> 2-> 3-> 4-> 5

() represents fast pointer
[] represents slow pointer

1. ([1]) -> 2 -> 3 -> 4 -> 5
   

2.  1 ->  [2]  -> (3) -> 4 -> 5


3.  1 ->  2 -> [3] -> 4 -> (5) 
   Reached the end of the list
       

Middle node: 3
Output: [3, 4, 5]

Case 2: Even number of nodes

6 nodes: 1-> 2-> 3-> 4-> 5-> 6

() represents fast pointer
[] represents slow pointer

1. ([1]) -> 2 -> 3 -> 4 -> 5 -> 6


2.  1 ->  [2] -> (3) -> 4 -> 5 -> 6


3.  1 ->  2 ->  [3] -> 4 -> (5) -> 6


4.  1 ->  2 ->  3 -> [4] -> 5 -> 6 -> (_)


Middle node: 4
Output: [4, 5, 6]

Implementation Code

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow

Javascript

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function middleNode(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}