Flatten the Multi-Level Linked List
You are provided with a multi-level linked list containing N
nodes. Each node has pointers next and child, which could potentially point to additional nodes. The task is to flatten this multi-level linked list into a single-level linked list and return the head of this singly linked list.
Input:
1. The integer 'T' representing the number of test cases. 2. Each test case contains multi-level linked list nodes in level-order form, represented by space-separated integers. For null pointers (next or child), use -1.
Output:
For every test case, output the flattened linked list as a sequence of node values in a single line.
Example:
Input:
T = 1
Multi-level list input: 10 5 4 12 -1 20 -1 7 -1 13 2 11 17 -1 16 -1 -1 -1 -1 -1 -1 -1 -1
Output:
10 5 12 7 11 17 4 20 13 16 2
Constraints:
1 <= T <= 10
0 <= N <= 10^4
1 <= data <= 10^9
- Time Limit: 1 sec
Note:
The format provided is to explain how the input is structured for a given multi-level linked list. The sequence is consolidated into a single line of space-separated integers for input purposes. You do not need to handle printing; simply focus on the implementation of functionality.
Flatten a multi-level linked list into a single-level linked list and return the head of the singly linked list.
Traverse the multi-level linked list using depth-first search (DFS).
Maintain a stack to ...read more
Top Microsoft Corporation Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in Microsoft Corporation Software Developer Intern
Reviews
Interviews
Salaries
Users/Month