Alternate Two Chains
EasyLinked List
Problem
A quiz app builds a session by taking questions alternately from two decks, each stored as a singly linked list: first from deck a, then from deck b, then a again, and so on.
When one deck runs out, the rest of the other deck follows in its original order. Given the heads a and b, splice the nodes accordingly and return the head of the session.
Example 1
- Input:
- a = [1, 2, 3], b = [10, 20, 30, 40, 50]
- Output:
- [1, 10, 2, 20, 3, 30, 40, 50]
After 3 and 30, deck a is empty, so 40 and 50 follow.
Example 2
- Input:
- a = [5], b = []
- Output:
- [5]
Constraints
- 0 ≤ nodes in each list ≤ 5000
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
The result alternates strictly until one list is empty. Which list goes first each round?
Walkthrough
How to approach it
01Clarify before coding
- Which list starts? Always a.
- Can either list be empty? Yes; the result is then the other list.
- Relink or copy? Relink the existing nodes.
02Brute force
Copy both lists into arrays, interleave the arrays and build a new list.
Cost: O(n + m) time and O(n + m) extra space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.