1613. Referral Order Copy
A referral programme is stored as a singly linked list where each node has a val, a next pointer and a random pointer to some node of the same list or to null; the random pointer means "this member was referred by that member". Build a brand new deep copy of the list in which every node appears after the node its random pointer points to. Among the nodes that may legally come next, always take the one with the smallest index in the original list (Kahn's algorithm with a min-heap). Each copied node's random pointer must point to the copy of the original target, and null stays null. If the random pointers form a cycle, a node pointing to itself included, return null; an empty list also returns null. The list has at most 1000 nodes. Time O(n log n), space O(n).
Example 1
- Input:
- head = [[5,2],[6,null],[7,1]]
- Output:
- [[6,null],[7,0],[5,1]]
- Explanation:
The node holding 6 has no referrer so it comes first, then 7 (it points to 6), then 5 (it points to 7).
Example 2
- Input:
- head = [[1,null],[2,null],[3,0]]
- Output:
- [[1,null],[2,null],[3,0]]
- Explanation:
The first two nodes are free and the smallest index goes first, so the order stays 1, 2, 3 and the last node points back to the first.
Example 3
- Input:
- head = [[4,0]]
- Output:
- []
- Explanation:
A node whose random pointer is itself forms a cycle, so the answer is null.
Constraints
0 ≤ length ≤ 1000
-104 ≤ val ≤ 104
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 log n)
- Space
- O(n)