Middle of the Parade

Easytwo pointersAlso known as Middle of the Linked List

A town parade is a line of floats. Each driver only knows which float is right behind them. Nobody has the full list, and nobody knows how long the parade is.

The TV crew wants to film from the float in the middle of the parade. Starting from the lead float and following "who is behind you" from float to float, find it.

Your task

Write middleFloat(head). head is the first node of a linked list (each node has val and next). Return the middle node.

With an odd number of floats there is one middle. With an even number there are two; return the second one. The tests read the list from the node you return to the end, so returning the middle node of [1, 2, 3, 4, 5] shows as [3, 4, 5].

middleFloat(head: ListNode) → ListNode

Examples

Example 1

Input

head = [8, 3, 6, 2, 9]

Output

[6, 2, 9]

Why

Five floats. The third, 6, has two floats ahead of it and two behind. From 6 the parade reads 6, 2, 9.

Example 2

Input

head = [8, 3, 6, 2]

Output

[6, 2]

Why

Four floats, so 3 and 6 are both in the middle. The rule picks the second one, 6. Returning 3 would show [3, 6, 2] and fail.

Constraints

1 ≤ number of floats ≤ 10,000
Float ids are integers and may repeat.
Return a node from the list you were given; do not build a new list.

Start with brute force

Walk the whole parade once to count the floats, n. Then walk again from the start and stop after n / 2 steps (rounded down).

That is O(n) and perfectly correct, but it needs two full passes. The point of this problem is a trick that finds the middle in a single pass without knowing n, which is what you need when the list is being read once, like a stream, or as part of a bigger list algorithm.

Hints

0 of 4 shown

Hint 1
Two friends start at the lead float. One walks one float at a time, the other skips ahead two at a time. Where is the slow one when the fast one runs out of parade?
Hint 2
The fast walker always covers twice the distance of the slow walker. So when the fast one reaches the end, the slow one has covered half the parade.
Hint 3
Be careful with the stopping rule. Try it on 2 floats and on 4 floats and check that the slow walker stops on the second middle.
Hint 4
Start slow and fast at head. While fast and fast.next both exist, move slow one step and fast two steps. Return slow.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

You do not know the length, but you do not need it. Send two pointers down the list at different speeds. When the fast one runs out of list, the slow one is halfway.

Trace 8 → 3 → 6 → 2 → 9:

slow = 8, fast = 8. fast has a next, so move: slow = 3, fast = 6.
fast = 6 has a next, so move: slow = 6, fast = 9.
fast = 9 has no next. Stop. Return slow, which is 6.

With 8 → 3 → 6 → 2: slow = 3 and fast = 6 after one move, then slow = 6 and fast = null after the second. The loop stops on fast === null and slow sits on the second middle, 6, as required. If you wanted the first middle instead, you would stop one step earlier by checking fast.next.next.

Reference solution

function middleFloat(head) {
  let slow = head;
  let fast = head;
  // fast moves 2 steps for every 1 step of slow
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

def middle_float(head):
    slow = fast = head
    # fast moves 2 steps for every 1 step of slow
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

TimeO(n)fast crosses the list once; slow makes half as many steps.

SpaceO(1)Two pointers, whatever the length.

Learn the idea: Linked Lists

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code