Flattening a multilevel linked list

Question

Question

1. Given a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list.

2. Given the head of the first list flatten the list so that all the nodes appear in a single-level linked list.

Goal.

We need to flatten the list in such a way that all nodes at first level should come first, then nodes of second level, and so on.

The above list should be converted to

10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15

My approach:

1) Create an empty queue
2) while(Queue is not empty AND head.next!=null AND head.child!=null)
     2a) while(head!=null)
           if(head.child!=null)
               Enqueue(head.child)
           newList = head;
           head = head.next;
           newList = newList.next;
     2b)head = deQ();

Is this approach correct?

Answer 1

Here's a simple two-finger breadth-first (level-order) traverse which does an in-place flattening. (Efficiency freaks might want to rearrange the loops because some tests are done twice, but it hardly makes a difference.) The basic idea is that there is an implicit queue consisting of the nodes between finger2 and finger1. finger1 walks forward across the level and every time it reaches a node with no right sibling, the "queue" is advanced by walking finger2 to the right until it finds a child, which is then appended at finger1 so that finger1 can keep moving to the right.

finger1 = finger2 = head;
while finger2 is not Null:
  while finger1.next is not Null: finger1 = finger1.next
  while finger2 is not Null and finger2.child is Null: finger2 = finger2.next
  if finger2 is not Null:
    finger1.next = finger2.child
    finger2.child = Null