1573. Echo Every Link
A message relay stores a chain of readings as a singly linked list, and each reading has to be repeated right after itself so that a noisy receiver hears it twice. Given head, insert a new node carrying the same value directly after every original node, so 1 -> 2 becomes 1 -> 1 -> 2 -> 2. The result is the head of the lengthened list, and an empty list stays empty (null). The original nodes keep their order and the head is unchanged for a non-empty list. The list has 0 to 500 nodes. You may do it with recursion or with a loop, but the intended solution is a single pass that splices each copy in place. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- head = [1,2]
- Output:
- [1,1,2,2]
- Explanation:
Each value is repeated, so 1,2 becomes 1,1,2,2.
Example 2
- Input:
- head = [3,3,3]
- Output:
- [3,3,3,3,3,3]
- Explanation:
Every node is doubled, giving six 3s.
Constraints
0 ≤ length ≤ 500
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)