Middle of the Linked List

Intuitionwhy the faster pointer identifies the middle

A singly linked list does not reveal its length or let you jump to an index, so counting first and then walking back is possible but requires two passes. Instead, make one pointer move one node at a time and another move two nodes at a time. When the faster pointer has covered the list, the slower pointer has covered half of it.

The stopping point also handles both list lengths correctly. For an odd-length list, fast reaches the last node and slow sits on the exact middle. For an even-length list, fast moves past the last node and slow has already advanced to the second of the two middle nodes. Returning slow therefore matches the required tie-breaking rule without a separate case.

Approach

1. 1Set slow and fast to head, because both pointers should begin at the same first node so their distance reflects the number of steps taken in the current traversal.
2. 2Continue while fast and fast->next are both non-null, because the next move must be safe for both pointers and the loop must stop when fast reaches or passes the list end.
3. 3Move slow by one node and fast by two nodes in the same loop iteration, because fast then covers twice as much distance and slow reaches half the list when fast finishes.
4. 4Return slow after the loop, because an odd-length list stops with fast on its final node while an even-length list stops after fast passes the end, leaving slow on the second middle node.

Complexityone traversal and two pointer variables

Annotated solutionC++ · one pass · constant extra space

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int value) : val(value), next(nullptr) {}
    ListNode(int value, ListNode* nextNode) : val(value), next(nextNode) {}
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

The condition checks fast->next before the body moves fast by two links. That guard is both a safety check and the reason the even-length case chooses the second middle: when fast passes the final node, slow has just taken the extra step needed to move from the first middle to the second.

The two-pass alternativea straightforward arrangement when counting feels clearer

You can first count n by walking from head to null, then walk n / 2 steps from head and return that node. This is not an optimization: it still takes O(n) time and O(1) extra space, while the fast pointer solution combines both passes into one traversal. It remains a reasonable alternative when the midpoint index is needed for another operation or when the direct speed argument is less familiar.

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int value) : val(value), next(nullptr) {}
    ListNode(int value, ListNode* nextNode) : val(value), next(nextNode) {}
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int length = 0;
        ListNode* current = head;

        while (current != nullptr) {
            ++length;
            current = current->next;
        }

        current = head;
        for (int steps = 0; steps < length / 2; ++steps) {
            current = current->next;
        }

        return current;
    }
};

Common mistakesthe two pointer details that change the returned node