LeetCode 876: Middle of the Linked List

Problem Restatement

We are given the head of a singly linked list.

We need to return the middle node of the linked list.

If the linked list has two middle nodes, we return the second middle node. For example, in a list with 6 nodes, nodes 3 and 4 are both middle candidates, so we return node 4. LeetCode states this rule explicitly.

Input and Output

Example function shape:

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    ...

Examples

Example 1:

Input:  head = [1,2,3,4,5]
Output: [3,4,5]

The list has 5 nodes.

The middle node is the 3rd node, whose value is 3.

Returning the node with value 3 means the visible output is:

[3,4,5]

because LeetCode displays the returned node and every node after it.

Example 2:

Input:  head = [1,2,3,4,5,6]
Output: [4,5,6]

The list has 6 nodes.

There are two middle nodes: value 3 and value 4.

The problem asks for the second middle node, so we return the node with value 4.

First Thought: Store Nodes in an Array

A simple way is to walk through the linked list and store every node in an array.

Then we return the node at index:

len(nodes) // 2

For odd length:

[1,2,3,4,5]

There are 5 nodes.

5 // 2 == 2

Index 2 is the node with value 3.

For even length:

[1,2,3,4,5,6]

There are 6 nodes.

6 // 2 == 3

Index 3 is the node with value 4, which is the second middle node.

Code:

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes = []

        curr = head
        while curr:
            nodes.append(curr)
            curr = curr.next

        return nodes[len(nodes) // 2]

This works, but it stores all nodes, so it uses extra memory.

Problem With the Array Approach

The array approach uses O(n) extra space.

We can do better because we only need one node: the middle node.

A linked list can be scanned with pointers. We do not need random access if we can arrange for one pointer to reach the middle exactly when another pointer reaches the end.

Key Insight

Use two pointers:

Both pointers start at head.

When fast reaches the end of the list, slow has moved about half as many steps.

That means slow is at the middle.

This also handles the even length rule correctly. Because both pointers start at head, when the list has an even number of nodes, slow stops at the second middle node.

Algorithm

Initialize:

slow = head
fast = head

Then move through the list while fast can still move two steps:

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

When the loop ends, return:

slow

For [1,2,3,4,5]:

Now fast.next is None, so the loop stops.

Return slow, which is node 3.

For [1,2,3,4,5,6]:

Now fast is None, so the loop stops.

Return slow, which is node 4.

Correctness

At the start, both slow and fast point to the head.

During each loop iteration, slow moves one node and fast moves two nodes.

Therefore, after k iterations:

slow has moved k steps
fast has moved 2k steps

The loop continues only while fast and fast.next both exist. This means fast can safely move two steps.

When the loop stops, fast has reached the end of the list or moved past the last node.

At that time, slow has moved half as many steps as fast.

So slow points to the middle node.

For an odd number of nodes, this is the unique middle node.

For an even number of nodes, this is the second middle node, because slow advances once more when fast moves from the second-to-last node to None.

Thus, the algorithm returns exactly the node required by the problem.

Complexity

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

Code Explanation

We start both pointers at the first node:

slow = head
fast = head

The slow pointer tracks the candidate middle node.

The fast pointer checks how far we are from the end.

The loop condition is:

while fast and fast.next:

This ensures fast.next.next is safe to access.

Inside the loop:

slow = slow.next
fast = fast.next.next

slow moves one step.

fast moves two steps.

When fast can no longer move two steps, the list has been fully measured by the fast pointer.

At that point, slow is at the middle node, so we return it:

return slow

Testing

Helper code for local testing:

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

def build_list(values):
    dummy = ListNode()
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

Tests:

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.middleNode(head)) == [3, 4, 5]

    head = build_list([1, 2, 3, 4, 5, 6])
    assert to_list(s.middleNode(head)) == [4, 5, 6]

    head = build_list([1])
    assert to_list(s.middleNode(head)) == [1]

    head = build_list([1, 2])
    assert to_list(s.middleNode(head)) == [2]

    head = build_list([1, 2, 3])
    assert to_list(s.middleNode(head)) == [2, 3]

    print("all tests passed")

run_tests()

Test meaning: