LeetCode 876 - Middle of the Linked List

The problem gives us the head of a singly linked list and asks us to return the middle node. A singly linked list is a sequence of nodes where each node contains a value and a pointer to the next node.

leetcodeeasylinked-listtwo-pointers

LeetCode Problem 876

Difficulty: 🟢 Easy
Topics: Linked List, Two Pointers

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks us to return the middle node. A singly linked list is a sequence of nodes where each node contains a value and a pointer to the next node. Unlike arrays, linked lists do not support direct indexing, so we cannot instantly jump to the middle element.

The important detail in this problem is how to handle lists with an even number of nodes. If there are two possible middle nodes, we must return the second one. For example, in the list [1,2,3,4,5,6], the two middle nodes are 3 and 4, and the correct answer is the node containing 4.

The input represents the head node of the linked list. The output is not just the value of the middle node, but the actual node itself. In LeetCode's representation, returning the node means the output will display the linked list starting from that node onward.

The constraints tell us that the list length is between 1 and 100. This is a very small input size, so even less efficient solutions would still run quickly. However, the problem is designed to teach linked list traversal techniques, especially the fast and slow pointer approach.

There are several important edge cases to consider. A list containing only one node should immediately return that node as the middle. A list with two nodes should return the second node because the problem specifies that the second middle should be chosen. Odd-length and even-length lists must both be handled correctly. Since the problem guarantees at least one node, we do not need to handle an empty list.

Approaches

A straightforward brute-force solution is to first traverse the linked list and count how many nodes it contains. Once we know the length, we can calculate the middle index using integer division. Then we traverse the list a second time until we reach that index and return the corresponding node.

This approach works because the middle position of a list of length n is always n // 2 when using zero-based indexing. For odd-length lists, this naturally points to the exact middle node. For even-length lists, integer division gives the second middle node automatically.

Although this solution is correct, it requires two separate passes through the linked list. While the runtime is still linear, it is not the most elegant or efficient approach conceptually.

The key observation for a better solution is that we can locate the middle node in a single traversal by using two pointers moving at different speeds. One pointer moves one step at a time, while the other moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be positioned at the middle.

This works because the fast pointer covers twice as much distance as the slow pointer. When the fast pointer has traversed the full list, the slow pointer has traversed exactly half of it. For even-length lists, the stopping condition naturally places the slow pointer on the second middle node, which matches the problem requirement.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Count nodes first, then traverse again to the middle
Optimal O(n) O(1) Use fast and slow pointers in a single traversal

Algorithm Walkthrough

  1. Initialize two pointers, slow and fast, both starting at the head of the linked list. The slow pointer will move one node at a time, while the fast pointer will move two nodes at a time.
  2. Continue traversing the list while both fast and fast.next are not None. This condition ensures that the fast pointer can safely move two steps forward without causing an error.
  3. During each iteration, move the slow pointer forward by one node. At the same time, move the fast pointer forward by two nodes.
  4. As the traversal progresses, the fast pointer moves through the list twice as quickly as the slow pointer. This means that when the fast pointer reaches the end of the list, the slow pointer will have reached the middle.
  5. Once the loop terminates, return the slow pointer. At this point, it points to the middle node. For even-length lists, it naturally lands on the second middle node because of how the loop condition works.

Why it works

The correctness comes from the relative speeds of the two pointers. For every two nodes the fast pointer traverses, the slow pointer traverses one node. Therefore, when the fast pointer has covered the entire list, the slow pointer has covered exactly half the distance. This invariant guarantees that the slow pointer ends at the middle node. In even-length lists, the fast pointer reaches the end only after the slow pointer advances into the second middle position.

Python Solution

# 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

The implementation starts by initializing two pointers at the head of the list. The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time.

The while loop continues as long as the fast pointer can still move forward safely. Inside the loop, both pointers are updated according to their intended speeds.

When the loop ends, the fast pointer has either reached the last node or moved beyond the list entirely. At that exact moment, the slow pointer is positioned at the middle node. Returning slow satisfies the problem requirements directly.

The implementation is concise because the fast and slow pointer technique naturally handles both odd-length and even-length lists without requiring separate logic.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow
}

The Go implementation follows exactly the same algorithm as the Python version. The main difference is the explicit use of nil instead of None.

Go requires slightly more verbose pointer syntax, using fast.Next instead of fast.next. Otherwise, the logic is identical. Since the problem guarantees at least one node, there is no need for special handling of an empty list.

Worked Examples

Example 1

Input:

[1,2,3,4,5]

Initial linked list:

1 -> 2 -> 3 -> 4 -> 5
Iteration slow fast
Start 1 1
1 2 3
2 3 5

At this point, fast.next is None, so the loop stops.

The slow pointer is at node 3, which is the correct middle node.

Output:

[3,4,5]

Example 2

Input:

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

Initial linked list:

1 -> 2 -> 3 -> 4 -> 5 -> 6
Iteration slow fast
Start 1 1
1 2 3
2 3 5
3 4 nil

The loop stops because fast becomes nil.

The slow pointer is at node 4, which is the second middle node.

Output:

[4,5,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most once by the pointers
Space O(1) Only two pointer variables are used

The algorithm performs a single traversal of the linked list. Although the fast pointer moves twice as quickly, the total work is still proportional to the number of nodes in the list. No extra data structures are allocated, so the space usage remains constant.

Test Cases

# Helper functions for testing

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

class Solution:
    def middleNode(self, head):
        slow = head
        fast = head

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

        return slow

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

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

    return dummy.next

# Test 1: Odd-length list
head = build_list([1, 2, 3, 4, 5])
assert Solution().middleNode(head).val == 3  # Standard odd-length case

# Test 2: Even-length list
head = build_list([1, 2, 3, 4, 5, 6])
assert Solution().middleNode(head).val == 4  # Must return second middle

# Test 3: Single node
head = build_list([1])
assert Solution().middleNode(head).val == 1  # Smallest valid input

# Test 4: Two nodes
head = build_list([1, 2])
assert Solution().middleNode(head).val == 2  # Second node is the answer

# Test 5: Three nodes
head = build_list([1, 2, 3])
assert Solution().middleNode(head).val == 2  # Exact middle

# Test 6: Four nodes
head = build_list([1, 2, 3, 4])
assert Solution().middleNode(head).val == 3  # Second middle in even list

# Test 7: Larger odd-length list
head = build_list([1, 2, 3, 4, 5, 6, 7])
assert Solution().middleNode(head).val == 4  # Middle of larger odd list

# Test 8: Larger even-length list
head = build_list([1, 2, 3, 4, 5, 6, 7, 8])
assert Solution().middleNode(head).val == 5  # Second middle in larger even list
Test Why
[1,2,3,4,5] Validates standard odd-length behavior
[1,2,3,4,5,6] Ensures second middle is returned
[1] Tests smallest possible input
[1,2] Confirms correct handling of two-node lists
[1,2,3] Tests minimal odd-length nontrivial case
[1,2,3,4] Tests minimal even-length nontrivial case
[1,2,3,4,5,6,7] Verifies behavior on larger odd-length lists
[1,2,3,4,5,6,7,8] Verifies behavior on larger even-length lists

Edge Cases

A single-node list is the smallest valid input. This case is important because some implementations may incorrectly assume that multiple nodes exist. In this implementation, both slow and fast start at the only node, and the loop never executes because fast.next is None. The function correctly returns the single node.

An even-length list is another critical edge case because the problem explicitly requires returning the second middle node. A naive implementation might accidentally return the first middle node instead. The fast and slow pointer approach naturally avoids this bug because the slow pointer advances one extra step before the loop terminates.

A two-node list is a particularly tricky special case of an even-length list. Some incorrect solutions stop too early and return the first node. In this implementation, the loop executes once, moving slow to the second node and fast beyond the list. The returned node is therefore correct.

Longer lists with alternating traversal lengths are also important for validating pointer movement logic. If the loop condition is written incorrectly, such as checking only fast without checking fast.next, the implementation may attempt to access a nonexistent node and crash. Using the condition while fast and fast.next prevents this issue safely.