Given a linked list where every node represents a linked list and contains two pointers of its type:
- Pointer to next node in the main list (we call it ‘right’ pointer in the code below).
- Pointer to a linked list where this node is headed (we call it the ‘down’ pointer in the code below).
All linked lists are sorted. See the following example
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
Write a function flatten() to flatten the lists into a single linked list. The flattened linked list should also be sorted. For example, for the above input list, output list should be 5->7->8->10->19->20->22->28->30->35->40->45->50.
The idea is to use the Merge() process of merge sort for linked lists. We use merge() to merge lists one by one. We recursively merge() the current list with the already flattened list.
The down pointer is used to link nodes of the flattened list.
Below is the implementation of the above approach:
Python3
# Python program for flattening # a Linked Listclass Node(): def __init__(self, data): self.data = data self.right = None self.down = Noneclass LinkedList(): def __init__(self): # Head of list self.head = None # Utility function to insert a # node at beginning of the # linked list def push(self, head_ref, data): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(data) # Make next of new Node as head new_node.down = head_ref # 4. Move the head to point to # new Node head_ref = new_node # 5. Return to link it back return head_ref def printList(self): temp = self.head while(temp != None): print(temp.data, end = " ") temp = temp.down print() # An utility function to merge two # sorted linked lists def merge(self, a, b): # If the first linked list is empty # then second is the answer if(a == None): return b # If second linked list is empty # then first is the result if(b == None): return a # Compare the data members of the # two linked lists and put the # larger one in the result result = None if (a.data < b.data): result = a result.down = self.merge(a.down,b) else: result = b result.down = self.merge(a,b.down) result.right = None return result def flatten(self, root): # Base Case if(root == None or root.right == None): return root # Recur for list on right root.right = self.flatten(root.right) # Now merge root = self.merge(root, root.right) # Return the root # It will be in turn merged with # its left return root# Driver codeL = LinkedList()''' Let us create the following linked list 5 -> 10 -> 19 -> 28 | | | | V V V V 7 20 22 35 | | | V V V 8 50 40 | | V V 30 45'''L.head = L.push(L.head, 30);L.head = L.push(L.head, 8);L.head = L.push(L.head, 7);L.head = L.push(L.head, 5);L.head.right =L.push(L.head.right, 20);L.head.right =L.push(L.head.right, 10);L.head.right.right =L.push(L.head.right.right, 50);L.head.right.right =L.push(L.head.right.right, 22);L.head.right.right =L.push(L.head.right.right, 19);L.head.right.right.right =L.push(L.head.right.right.right, 45);L.head.right.right.right =L.push(L.head.right.right.right, 40);L.head.right.right.right =L.push(L.head.right.right.right, 35);L.head.right.right.right =L.push(L.head.right.right.right, 20);# Flatten the listL.head = L.flatten(L.head);L.printList()# This code is contributed by maheshwaripiyush9 |
Output:
5 7 8 10 19 20 20 22 30 35 40 45 50
Time Complexity: O(N*N*M) – where N is the no of nodes in main linked list (reachable using right pointer) and M is the no of node in a single sub linked list (reachable using down pointer).
Space Complexity: O(N*M) as the recursive functions will use recursive stack of size equivalent to total number of elements in the lists.
Please refer complete article on Flattening a Linked List for more details!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
