#876 Middle of the Linked List
the problem
In plain words
Return the middle node of a singly linked list. If there are two middle nodes, return the second one.
in head = [1,2,3,4,5]
out [3,4,5]
Node 3 is the middle.
in head = [1,2,3,4,5,6]
out [4,5,6]
Two middles (3 and 4) — return the second.
- 1 ≤ number of nodes ≤ 100
- 1 ≤ Node.val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFast & slow pointers
Two pointers from the start, one twice as fast: when the fast one reaches the end, the slow one is halfway.
solutions
From brute force to optimal
Arrays have O(1) indexing — store the nodes and return index n/2.
- Add each node to an ArrayList.
- Return nodes.get(size / 2).
One pass.
The list of node references.
class Solution { public ListNode middleNode(ListNode head) { List<ListNode> nodes = new ArrayList<>(); for (ListNode p = head; p != null; p = p.next) nodes.add(p); return nodes.get(nodes.size() / 2); // second middle when the size is even }}First pass counts n; second pass walks n/2 steps.
- Count nodes.
- Walk n/2 hops from head.
1.5 passes.
A counter and a pointer.
class Solution { public ListNode middleNode(ListNode head) { int n = 0; for (ListNode p = head; p != null; p = p.next) n++; ListNode p = head; for (int i = 0; i < n / 2; i++) p = p.next; return p; }}fast moves 2, slow moves 1; stop when fast can't move two.
- slow = fast = head.
- While fast != null && fast.next != null: slow = slow.next; fast = fast.next.next.
- Return slow.
fast walks the list once.
Two references.
class Solution { public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify which middle for even lengths — this loop condition gives the second.
- Mention that
while (fast.next != null && fast.next.next != null)gives the first middle — that's the variant used to split a list for merge sort or Reorder List.
traps
- Checking only
fast.next != null: when fast itself is null (even length),fast.nextthrows. - Using
fast.next != null && fast.next.next != nullhere — that stops on the first middle, but this problem wants the second.
what they ask next
Follow-ups
Delete the Middle Node (LC 2095)?
Start fast one step ahead (or keep a prev behind slow) so slow stops before the middle, then unlink it.
before you submit
Edge cases to test
- One node → that node.
- Two nodes → the second node.
- Even length → the second of the two middles.
practise next
Similar problems
- #234Palindrome Linked ListEasyin Linked Lists
- #143Reorder ListMediumin Linked Lists
- #148Sort ListMediumin Sorting