Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Flattening a Linked List

Medium Acceptance 51.53% Points 30.00

You are given a linked list where each node contains two pointers:

  1. next pointer**:** Points to the next node in the main linked list.
  2. bottom pointer**:** Points to the head of another sorted sub-linked list.

Each sub-linked list is sorted in ascending order. Flatten the Link List so all the nodes appear in a single level while maintaining the sorted order.

Note: The flattened linked list should be printed using the bottom pointer instead of the next pointer. Refer to the printList() function in the driver code for better understanding.

Examples
Example 1

Example 1

Input: 5 -> 10 -> 19 -> 28 | | | | 7 20 22 35 | | | 8 50 40 | | 30 45

Output: 5->7->8->10->19->20->22->28->30->35->40->45->50

Explanation: The resultant linked lists has every node in a single level.(Note: | represents the bottom pointer.)

Hints
Hint 1
Expected Time Complexity: O(nnm)
Hint 2
Expected Space Complexity: O(n)
Constraints
  • 0 <= number of nodes <= 50
  • 1 <= no. of nodes in sub-LinkesList(mi) <= 20
  • 1 <= node->data <= 10^3
Companies
Amazon Microsoft Visa Goldman Sachs Flipkart + 1 more
Topics
Linked List
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions