Flatten a Multilevel Sorted Linked List

You are given a linked list with 'N' nodes, where each node contains two pointers: one is 'NEXT' pointing to the next node in the list, and the other is 'CHILD', pointing to a sorted child linked list. Your task is to flatten this linked list so that all nodes appear in a single level while maintaining sorted order.

Input:

The first line contains an integer 'T', the number of test cases.
Each test case starts with an integer 'N', indicating the number of nodes in the primary linked list.
For the next 'N' lines, each contains space-separated integers representing the child nodes of the current node, ending with -1 to indicate the end of the sublist.

Output:

For each test case, return the head node of the flattened linked list.

Example:

The given linked list looks like this:
// Image depiction
The output should be:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.

Constraints:

  • 1 <= T <= 5
  • 1 <= N <= 100
  • 1 <= C <= 20
  • 1 <= data <= 1000
  • Time Limit: 1 second

Note:

The flattened list uses the 'BOTTOM' pointer instead of the 'NEXT' pointer. The value of any node will not be equal to -1.

AnswerBot
4d

Flatten a multilevel sorted linked list while maintaining sorted order.

  • Iterate through the linked list nodes and maintain a stack to keep track of child nodes.

  • Merge the child nodes with the parent nod...read more

Help your peers!
Add answer anonymously...
Morgan Stanley Technology Analyst 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