Flattening a Linked List | GeeksforGeeks
Better to use Heap:
1.) Use a min heap of size n containing the first nodes of each column. This will use O((m + n)logn) time and O(n) space
Write a function flatten() to flatten the lists into a single linked list. The flattened linked list should also be sorted.
The idea is to use Merge() process of merge sort for linked lists. We use merge() to merge lists one by one. We recursively merge() the current list with already flattened list.
Java Code:
Read full article from Flattening a Linked List | GeeksforGeeks
Given a linked list where every node represents a linked list and contains two pointers of its type:
(i) Pointer to next node in the main list (we call it ‘right’ pointer in below code)
(ii) Pointer to a linked list where this node is head (we call it ‘down’ pointer in below code).
All linked lists are sorted. See the following example
(i) Pointer to next node in the main list (we call it ‘right’ pointer in below code)
(ii) Pointer to a linked list where this node is head (we call it ‘down’ pointer in below code).
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 Merge() process of merge sort for linked lists. We use merge() to merge lists one by one. We recursively merge() the current list with already flattened list.
The down pointer is used to link nodes of the flattened list.
The down pointer is used to link nodes of the flattened list.
Better to use Heap:
1.) Use a min heap of size n containing the first nodes of each column. This will use O((m + n)logn) time and O(n) space
Write a function flatten() to flatten the lists into a single linked list. The flattened linked list should also be sorted.
The idea is to use Merge() process of merge sort for linked lists. We use merge() to merge lists one by one. We recursively merge() the current list with already flattened list.
Node* merge( Node* a, Node* b )
{
// If first list is empty, the second list is result
if
(a == NULL)
return
b;
// If second list is empty, the second list is result
if
(b == NULL)
return
a;
// Compare the data members of head nodes of both lists
// and put the smaller one in result
Node* result;
if
( a->data < b->data )
{
result = a;
result->down = merge( a->down, b );
}
else
{
result = b;
result->down = merge( a, b->down );
}
return
result;
}
// The main function that flattens a given linked list
Node* flatten (Node* root)
{
// Base cases
if
( root == NULL || root->right == NULL )
return
root;
// Merge this list with the list on right side
return
merge( root, flatten(root->right) );
}
Java Code:
class
LinkedList
{
Node head;
// head of list
/* Linked list Node*/
class
Node
{
int
data;
Node right, down;
Node(
int
data)
{
this
.data = data;
right =
null
;
down =
null
;
}
}
// An utility function to merge two sorted linked lists
Node merge(Node a, Node b)
{
// if first linked list is empty then second
// is the answer
if
(a ==
null
)
return
b;
// if second linked list is empty then first
// is the result
if
(b ==
null
)
return
a;
// compare the data members of the two lonked lists
// and put the larger one in the result
Node result;
if
(a.data < b.data)
{
result = a;
result.down = merge(a.down, b);
}
else
{
result = b;
result.down = merge(a, b.down);
}
return
result;
}
Node flatten(Node root)
{
// Base Cases
if
(root ==
null
|| root.right ==
null
)
return
root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return
root;
}
}