Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Convert multi level linked list into single level

Write an efficient algorithm to convert multi level linked list into single level. In this problem every node has two pointer next and child pointer. View structure of this linked list.

Example

Given in below examples of view to multi level linked list.

Example

Solve this program using queue.

For example suppose given linked list contain following nodes.

12345786101112913 Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 1next (pointer) child (pointer) struct Nodedata (int)= 2next (pointer) child (pointer)= NULLstruct Nodedata (int)= 3next (pointer) child (pointer)= NULLstruct Nodedata (int)= 4next (pointer)= NULLchild (pointer) struct Nodedata (int)= 5next (pointer) child (pointer)= NULLstruct Nodedata (int)= 6next (pointer)= NULLchild (pointer) struct Nodedata (int)= 10next (pointer)= NULLchild (pointer)= NULLstruct Nodedata (int)= 7next (pointer) child (pointer) struct Nodedata (int)= 8next (pointer) child (pointer)= NULLstruct Nodedata (int)= 9next (pointer)= NULLchild (pointer)= NULLstruct Nodedata (int)= 11next (pointer) child (pointer) struct Nodedata (int)= 12next (pointer)= NULLchild (pointer)= NULLstruct Nodedata (int)= 13next (pointer)= NULLchild (pointer)= NULL

After arrange.

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 1next (pointer) child (pointer)= NULLstruct Nodedata (int)= 2next (pointer) child (pointer)= NULLstruct Nodedata (int)= 3next (pointer) child (pointer)= NULLstruct Nodedata (int)= 4next (pointer) child (pointer)= NULLstruct Nodedata (int)= 5next (pointer) child (pointer)= NULLstruct Nodedata (int)= 6next (pointer) child (pointer)= NULLstruct Nodedata (int)= 10next (pointer) child (pointer)= NULLstruct Nodedata (int)= 7next (pointer) child (pointer)= NULLstruct Nodedata (int)= 8next (pointer) child (pointer)= NULLstruct Nodedata (int)= 9next (pointer) child (pointer)= NULLstruct Nodedata (int)= 11next (pointer) child (pointer)= NULLstruct Nodedata (int)= 12next (pointer) child (pointer)= NULLstruct Nodedata (int)= 13next (pointer)= NULLchild (pointer)= NULL

View code animation

Program for convert multi level linked list into single level. Time complexity O(n).

Output

Submit your solution in comment section.

Spread the post

Recommended Posts: