Flattening a Linked List

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 

Author: Hrishikesh Mishra