Middle of the Linked List

Q: What is the time and space complexity of finding the middle of a linked list?

All three approaches take O(n) time, since the middle cannot be found without walking about half the list or more. Copying the values uses O(n) extra memory. Counting first and the fast and slow pointers both use O(1) , and the pointers need only one pass.

EasyFast and slow pointers Linked list

+10

You get a singly linked list stored in two arrays of the same length. Node i holds the value values[i] and links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, so follow the links.

Return the value of the middle node. When the list has an even number of nodes there are two middle nodes; return the value of the second one.

Function

middleNode(values: integer-array, next: integer-array) → integer

valuesinteger-array: the value held by each node
nextinteger-array: the index of the node each node links to, or -1 for the last node
Returnsinteger: the value of the middle node, the second middle one when the length is even

Constraints

1 ≤ n ≤ 5000, where n is the length of values and of next.
-10⁴ ≤ values[i] ≤ 10⁴
Each next[i] is -1 or a node index from 0 to n-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
Output: 5
Explanation: Following the links from node 0 gives nodes 0, 3, 4, 2, 1, so the list reads 4, 7, 5, 2, 9. The third of the five is node 4, whose value is 5. The array's own middle entry, values[2] = 2, is a different node.

Input: values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
Output: 40
Explanation: Here the nodes are stored in order. Six nodes have two middle ones, 30 and 40, and the second one wins.

+13 hidden tests on Submit

Follow-up

Can you return the node one third of the way down the list in a single pass? How fast would each pointer move, and where would you stop?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

In an array the middle is at index n / 2. A linked list gives you no index: you only learn how long it is by walking to the end, and by then you have passed the middle. You can copy the list into an array, or count first and walk again. The neat answer sends two pointers down the list at different speeds, so that the slow one is halfway when the fast one runs out.

Copy the values into an array

Intuition

In this problem a pointer is a node index. Moving to the next node is node = next[node], and reaching -1 means you have walked off the end. In the first example the walk from node 0 goes 0 → 3 → 4 → 2 → 1 → -1.

The trouble with a list is that you cannot jump to a position. So turn it into something you can: walk the list once and append each value to a new array as you pass it. That array holds the values in list order, [4, 7, 5, 2, 9] for the first example, and its middle is at index length / 2 with integer division.

That index gives the second middle for an even length on its own: six values give index 3, the fourth value, which is 40 in the second example. The walk costs O(n) time, and the copy costs O(n) extra memory, which the next two approaches avoid.

Algorithm

Start with an empty array and node = 0.
While node is not -1, append values[node] and move to next[node].
Return the entry at index length / 2, rounded down.

def middleNode(values, next):
    in_order = []
    node = 0
    while node != -1:
        in_order.append(values[node])
        node = next[node]
    return in_order[len(in_order) // 2]

Count, then walk half way

Intuition

You do not need the whole copy, only the length. Walk the list once and count the nodes. Then start again at the head and take length / 2 steps, rounded down. The node you stop on is the middle.

Why that many steps: after k steps you stand on the node at position k, counting the head as position 0. The middle of a list of 5 is position 2, and the second middle of a list of 6 is position 3, both length / 2. In the first example you count 5, take two steps 0 → 3 → 4, and read values[4] = 5.

The memory is now O(1). The cost is a second trip over half the list, 1.5n moves in total, which is still O(n).

Algorithm

Walk from node 0 to -1 and count the nodes.
Go back to node 0.
Move node = next[node] exactly count / 2 times, rounded down.
Return values[node].

def middleNode(values, next):
    length = 0
    node = 0
    while node != -1:
        length += 1
        node = next[node]
    node = 0
    for _ in range(length // 2):
        node = next[node]
    return values[node]

Fast and slow pointers

Intuition

Put two pointers on the head. Each round, slow moves one node and fast moves two. After k rounds slow stands at position k and fast at position 2k, so slow has always covered half of fast's distance. When fast reaches the end, slow is in the middle, and you never needed the length.

The stopping rule decides which middle you get. Keep going while fast is a real node and has a node after it: fast != -1 and next[fast] != -1. With an odd length fast stops on the last node. With an even length fast steps off the end to -1, which pushes slow one further, onto the second middle. In the second example slow goes 0, 1, 2, 3 while fast goes 0, 2, 4, -1, and values[3] is 40.

In the first example slow visits nodes 0, 3, 4 while fast visits 0, 4, 1; node 1 is the last one, so the loop stops with slow on node 4 and the answer 5. Fast makes about n moves and slow n / 2, in a single pass and with two integers of memory.

Algorithm

Set slow = 0 and fast = 0.
While fast != -1 and next[fast] != -1, set slow = next[slow] and fast = next[next[fast]].
Return values[slow].

def middleNode(values, next):
    slow = fast = 0
    # Stop when fast is on the last node or has stepped past it.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    return values[slow]

Pitfalls and edge cases

The loop is short, so the mistakes sit in where it starts, where it stops, and what it returns.

Returning values[n / 2]. The nodes are not stored in list order, so the array's middle entry is usually some other node. In the first example it gives 2 instead of 5.
Getting the first middle on an even length. A loop that runs while next[fast] and next[next[fast]] are both real stops one round early and returns 30 instead of 40 in the second example.
Checking next[fast] before fast != -1. On an even length fast becomes -1, and reading next[-1] crashes in most languages. In Python it silently reads the last entry instead, which is worse.
Walking count / 2 - 1 or rounding up in the counting approach. Count the head as position 0 and take exactly count / 2 steps, rounded down.
Returning the node index instead of its value.
Forgetting the offset in Lua and R, where arrays start at 1. Keep node indexes 0-based and read next[node + 1]. Ruby and R reserve the word next, so their starters name the parameter next_.

Frequently asked questions4

Why do fast and slow pointers find the middle of a linked list?

Both start at the head, and each round the fast pointer moves two nodes while the slow one moves one. After k rounds the fast pointer is at position 2k and the slow one at k, exactly half as far. So when the fast pointer reaches the end of the list, the slow one is at its middle.

What is the time and space complexity of finding the middle of a linked list?

All three approaches take O(n) time, since the middle cannot be found without walking about half the list or more. Copying the values uses O(n) extra memory. Counting first and the fast and slow pointers both use O(1), and the pointers need only one pass.

How do you return the first middle node instead of the second?

Change the stopping rule so the fast pointer stops one round earlier: loop while next[fast] != -1 and next[next[fast]] != -1. For six nodes the slow pointer then stops on position 2 instead of 3. In the counting approach, walk (count - 1) / 2 steps instead of count / 2.

Where else is the fast and slow pointer technique used?

The same two speeds detect a cycle in a linked list: in a loop the fast pointer laps the slow one and they meet. They also find where a cycle starts, and they split a list in half for merge sort or for checking whether a list reads the same in both directions.

Python

def middleNode(values, next):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

values = [4, 9, 2, 7, 5]
next = [3, -1, 1, 4, 2]

Expected

Middle of the Linked List

Function

Constraints

Examples

Hints

Solution

Copy the values into an array

Count, then walk half way

Fast and slow pointers

Pitfalls and edge cases

Frequently asked questions4

Similar problems