How do you approach Middle of the Linked List?

A first pass could count the nodes, then a second pass could stop at index count / 2.

What is the time complexity of Middle of the Linked List?

Time complexity: O(n) - single pass. Space complexity: O(1) extra (O(n) for the returned suffix).

What are common mistakes on Middle of the Linked List?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Middle of the Linked List

EasyData Structures

Description

Given the head of a singly linked list, return the middle node of the linked list and everything after it.

If there are two middle nodes, return the second middle node onward.

Note: For this problem, linked lists are represented as arrays for simplicity. The function takes the list as an array and should return the array starting at the middle node.

Example 1

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

Output: [3,4,5]

Explanation: The middle node of the list is node 3.

Example 2

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

Output: [4,5,6]

Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Example 3

Input: head = [1]

Output: [1]

Constraints

- The number of nodes in the list is in the range [1, 100]. - 1 <= Node.val <= 100

Middle of the Linked List: approach, complexity and pitfalls

An easy linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

A first pass could count the nodes, then a second pass could stop at index count / 2.
Can you do it in a single pass? Think about moving two pointers at different speeds.
Advance a fast pointer two steps for every one step of a slow pointer - when fast hits the end, slow is at the middle (the second middle for even-length lists).

The optimal approach

Show the approach: Fast & Slow Pointers

Move a slow pointer one step and a fast pointer two steps at a time. When the fast pointer can no longer advance, the slow pointer sits exactly on the middle node (the second middle when the length is even). Return everything from the slow pointer onward.

Time: O(n) - single pass
Space: O(1) extra (O(n) for the returned suffix)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.