Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 15 minutes
The problem we are exploring is to flatten a singly linked list. The initial singly linked list (to be flattened) has nodes of the following type:
(1) Pointer to next node in the main list (we call it โrightโ pointer in code)
(2) Pointer to a sorted linked list where this node is head (we call it โdownโ pointer in code).
Flattening a linked list should generate a linked list with nodes of the following type:
(1) Only one pointer to the next node
(2) All nodes are sorted based on data
For instance: the singly linked list is as follows:
1 -> 5 -> 7 -> 30
| | | |
V V V V
2 11 10 40
| | |
V V V
6 15 50
|
V
9
After flattening the above linked list, the resultant linked list should be:
1 -> 2 -> 5 -> 6 -> 7 -> 9 -> 10 -> 11 -> 15 -> 30 -> 40 -> 50
Approach
The approach towards solving this is to use the key idea of:
- Merging in merge sort algorithm
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.
Pseudocode
// The merge component of merge sort in Linked List
Node merge(Node a, Node b)
{
if (a == null) return b;
if (b == null) return a;
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;
}
// Utility to flatten the linked list
Node flatten(Node root)
{
if (root == null || root.right == null)
return root;
root.right = flatten(root.right);
root = merge(root, root.right);
return root;
}
Complexity
- Worst case time complexity:
ฮ(N ^ (2*K)) - Average case time complexity:
ฮ(N ^ (2*K)) - Best case time complexity:
ฮ(N ^ 2) - Space complexity:
ฮ(1)
where n is the number of down linked lists and k is the average size of the linked lists.
Implementations
- Java
Java
class LinkedList
{
static Node head; // head of linked list
private class Node
{
int data;
Node right, down;
Node(int d)
{
data = d;
right = null;
down = null;
}
}
Node merge(Node a, Node b)
{
if (a == null) return b;
if (b == null) return a;
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)
{
if (root == null || root.right == null)
return root;
root.right = flatten(root.right);
root = merge(root, root.right);
return root;
}
public Node add(Node head_ref, int data)
{
Node new_node = new Node(data);
new_node.down = head_ref;
head_ref = new_node;
return head_ref;
}
public void print_list()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+"->");
temp = temp.down;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
LinkedList L = new LinkedList();
L.head = L.add(L.head, 9);
L.head = L.add(L.head, 6);
L.head = L.add(L.head, 2);
L.head = L.add(L.head, 1);
L.head.right = L.add(L.head.right, 11);
L.head.right = L.add(L.head.right, 5);
L.head.right.right = L.add(L.head.right.right, 15);
L.head.right.right = L.add(L.head.right.right, 10);
L.head.right.right = L.add(L.head.right.right, 7);
L.head.right.right.right = L.add(L.head.right.right.right, 50);
L.head.right.right.right = L.add(L.head.right.right.right, 40);
L.head.right.right.right = L.add(L.head.right.right.right, 30);
L.head = L.flatten(L.head);
L.print_list();
}
}
