Middle of the Linked List
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
- 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, wherenis the length ofvaluesand ofnext.-104 ≤ values[i] ≤ 104- Each
next[i]is-1or a node index from0ton-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
0visits nodes0, 3, 4, 2, 1, which read4, 7, 5, 2, 9. The middle is node4, value5, not the array's middle entryvalues[2] = 2.
- 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,
30and40, and the second one wins.
- Input
- values = [8]next = [-1]
- Output
- 8
- Explanation
- A list of one node is its own middle.
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.
You do not know the length of the list until you reach its end. What if two walkers started at the head and one of them moved twice as fast as the other?
When the faster walker has reached the end, the slower one has covered half the distance, so it stands on the middle node. The only detail left is when to stop so that an even length lands on the second middle.
Start
slowandfastat node0. Whilefastis not-1andnext[fast]is not-1, move slow one link and fast two links. Then returnvalues[slow].
Solution
A linked list gives you no index: you learn its length only by walking to the end, past the middle. You can copy it into an array, or count first and walk again. Two pointers at different speeds need one pass: the slow one is halfway when the fast one runs out.
Copy the values into an array
Intuition
Walk the list once and append each value to an array: [4, 7, 5, 2, 9] in the first example. The array holds the values in list order, so its middle is at index length / 2 with integer division. On an even length that is the second middle: six values give index 3, the 40 of the second example. The walk costs O(n) time and the copy O(n) extra memory.
Algorithm
- Start with an empty array and
node = 0. - While
nodeis not-1, appendvalues[node]and move tonext[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 need only the length, not the copy. Count the nodes, go back to the head and take length / 2 steps, rounded down. After k steps you stand at position k, counting the head as 0, and length / 2 is the middle: position 2 of 5, and the second middle, position 3, of 6. In the first example you count 5, step 0 → 3 → 4 and read values[4] = 5.
Memory drops to O(1). The cost is a second trip over half the list, 1.5n moves in total.
Algorithm
- Walk from node
0to-1and count the nodes. - Go back to node
0. - Move
node = next[node]exactlycount / 2times, 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
Each round slow moves one node and fast moves two, so after k rounds slow is at position k and fast at 2k. When fast reaches the end, slow is in the middle, and you never needed the length.
The stopping rule picks which middle you get. Loop while fast != -1 and next[fast] != -1. With an odd length fast stops on the last node. With an even length it steps off to -1, which carries slow one node further, onto the second middle. In the second example slow goes 0, 1, 2, 3 while fast goes 0, 2, 4, -1, so the answer is values[3] = 40. It takes one pass and two integers of memory.
Algorithm
- Set
slow = 0andfast = 0. - While
fast != -1andnext[fast] != -1, setslow = next[slow]andfast = 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
- Returning
values[n / 2]. The nodes are not stored in list order, so in the first example that gives2instead of5. - Getting the first middle on an even length. A loop that runs while
next[fast]andnext[next[fast]]are both real stops one round early and returns30instead of40in the second example. - Checking
next[fast]beforefast != -1. On an even length fast becomes-1, and readingnext[-1]crashes in most languages. In Python it silently reads the last entry. - Walking
count / 2 - 1steps, or rounding up, in the counting approach. Count the head as position0.
Frequently asked questions3
What is the time and space complexity of finding the middle of a linked list?
All three approaches take O(n) time, since you must walk at least half the list. 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.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def middleNode(values, next):
# Write code hereTest #1
Test #2
Test #3
Arguments
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Expected Output
5