← Back to problems Solve on LeetCode → See #206 Reverse Linked List →

Middle of the Linked List

LeetCode 876 • Easy • Linked Lists

Input: head = [1, 2, 3, 4, 5] → Output: node 3
Return the middle node. If two middle nodes, return the second middle.

TimeO(n)single pass

SpaceO(1)only two pointers

Iterations: 0 Slow: — Fast: —

Slow (tortoise)

Fast (hare)

Middle

Slow

—

Fast

—

Result

pending

Speed:

Ready

Press Play to watch the fast & slow pointer technique find the middle, or Step to advance one operation.
Slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle.

✎ Whiteboard

Size:3

⌨ Type It — Two Pointer

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ MIDDLE OF LINKED LIST — TWO POINTER ═══

PATTERN ▸ Fast & slow pointer O(n) · O(1)

① SETUP — BOTH AT HEAD

slow = head

fast = head

② LOOP — FAST HAS ROOM

while fast and fast.next:

③ MOVE — SLOW 1, FAST 2

slow = slow.next

fast = fast.next.next

④ RETURN MIDDLE

return slow

Vars: slow, fast

▼ your implementation ▼

⌨ Type It — Recursive

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ MIDDLE OF LINKED LIST — RECURSIVE ═══

PATTERN ▸ Recursive fast & slow O(n) · O(n)

① DEFINE HELPER

def helper(slow, fast):

② BASE CASE — FAST AT END

if not fast or not fast.next:

return slow

③ RECURSE — ADVANCE BOTH

return helper(slow.next, fast.next.next)

④ ENTRY POINT

return helper(head, head)

▼ your implementation ▼

Verify your solution: