Middle of the Linked List
Easy · Two Pointers · Linked List · Two Pointers
Problem
You are given the head of a non-empty singly linked list. Walk the list and return the node that sits in the middle.
When the list has an even number of nodes there are two middle candidates; in that case return the second of the two. The answer is shown as the list that starts from the returned node.
Examples
Input: head = [4,8,15,16,23] Output: [15,16,23]
Five nodes, so the third node (value 15) is the middle.
Input: head = [7,1,9,2] Output: [9,2]
With four nodes the middles are 1 and 9; the second one, 9, is returned.
Input: head = [5] Output: [5]
A single node is its own middle.
Constraints
- The list has between 1 and 100 nodes
- 1 <= Node.val <= 100
Approaches
- Baseline: copy the nodes into an array — time O(n), space O(n)
Follow-up
What if you had to stop on the first middle instead, as merge sort needs when it splits a list? Loop while fast.next and fast.next.next. And to delete the middle you need the node before it: the use cases below ask both.
Related problems
Start free on Cariara · Coding problems · System design studio
