Flattening a Linked List

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(); 
    } 
}