Bootcamps
Masterclasses
Menu
Courses
Account
Login / Sign Up

Flattening a Linked List

Medium Acceptance 51.53% Points 30

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.)

Constraints
  • 0 <= number of nodes <= 50
  • 1 <= no. of nodes in sub-LinkesList(mi) <= 20
  • 1 <= node->data <= 10^3
Hints
  • Expected Time Complexity: O(nnm)
  • Expected Space Complexity: O(n)
Topics
Linked List
Companies
Amazon Microsoft Visa Goldman Sachs Flipkart Paytm
Added 07 Dec 2024 51.53% acceptance
Ln 1, Col 1Sign in to save your code
2 1 3 2 1
1 2
3
4 5 6
7 8
9
1 2 3 4 5 6 7 8 9