Flattening a Linked List
- Given a linked list where every node represents a linked list and contains two pointers of its type:
- Pointer to next node in the main list (we call it ‘right’ pointer in below code)
- Pointer to a linked list where this node is head (we call it ‘down’ pointer in below code).
- All linked lists are sorted. See the following example
5 -> 10 -> 19 -> 28 | | | | V V V V 7 20 22 35 | | | V V V 8 50 40 | | V V 30
Algorithm :
- Create result merge list head and node
- Iterate top node right pointer from left to right
- Call sorted list merger with result merge list node and one list
- Return head of merged list
Github: LinkedListFlattener.java
Output:
List:1 - 5 7 8 30 List:2 - 10 20 List:3 - 19 22 50 List:4 - 28 35 40 45 Merged list: 5 7 8 10 19 20 22 28 30 35 40 45 50