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.

AnswerBot
3d

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

Help your peers!
Add answer anonymously...
Microsoft Corporation Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter