Skip to main content

876. Middle of the Linked List

easy

Find the middle node of a singly linked list in one pass with two pointers. The slow/fast pointer pattern in its purest form — every later linked-list trick (cycle detection, palindrome check, sort-list split) reuses this primitive.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Constraints

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

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A two-pass solution counts the length first, then walks length/2 nodes. Can you do it in one pass?

Hint 2

Use two pointers that move at different speeds. If the fast one moves twice as fast, where is the slow one when fast hits the end?

Hint 3

Initialize slow = fast = head. Advance slow by one and fast by two each step. When fast or fast.next is null, slow is at the middle.

Solution approach

Reveal approach

Slow/fast two-pointer (the runner technique). Initialize slow = head and fast = head. Loop while fast is not null and fast.next is not null: advance slow by one (slow = slow.next) and fast by two (fast = fast.next.next). When the loop exits, fast has reached the end and slow is at the middle. For an even-length list, this returns the second of the two middle nodes — which is exactly what the problem asks for. O(n) time, O(1) extra space. Note: if the problem asked for the first middle node on even lengths, you'd use a different loop condition (while fast.next and fast.next.next).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • fast-slow-pointers
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

More Linked Lists practice problems

See all Linked Lists problems →