CODEWITHSUNDEEP
algorithmlinked-listqueuepseudocode
Dubby
Dubby

Reputation: 1144

Flattening a multilevel linked list

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.

enter image description here

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?

Upvotes: 4

Views: 3040

Answers (2)

Vishal Sahu
Vishal Sahu

Reputation: 790

Simple stack based solution which traverses till next ends, then attaches the children from stack.

node *flatten(node *head) {
    stack<node *> s;
    node *curr = root;
    while (1) {
        if (curr->next) { // keep moving in current streak
            if (curr->child)
                s.push(curr);
            curr = curr->next;
        }
        else { // attach child branch and continue from there
            if (s.empty())
                return head;
            curr->next = s.top()->next;
            s.top()->next = NULL;
            s.pop();
            curr = curr->next;
        }
    }
}

Upvotes: 0

rici
rici

Reputation: 241901

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

Upvotes: 3

Related Questions