Flattening a Linked List

Intuition

Each node has a next pointer (horizontal) and a child pointer (vertical sorted list). Merge all vertical lists using merge sort logic.

Algorithm

1Recursively flatten from right to left.
2Merge current node's child list with the already-flattened rest.
3Return merged sorted list.

Common Pitfalls

•After merging, the result uses child pointers, not next pointers. Set next to null in the merged result.

Flattening a Linked List.java

Java

// Approach: Use merge sort approach: recursively flatten the right chain, then merge current column with flattened.
// Time: O(n * m) Space: O(n)
class Node {
    int data;
    Node next;
    Node bottom;

    Node(int x) {
        data = x;
        next = null;
        bottom = null;
    }
}

class Solution {
    public Node flatten(Node node) {
        if (node == null || node.next == null)
            return node;
        Node temp = node;
        while (temp.next.next != null)
            temp = temp.next;
        // merge the last node and bottom of previous node
        Node mergedList = mergeList(temp.bottom, temp.next);

        temp.bottom = mergedList;
        temp.next = null;
        return flatten(node);
    }

    public Node mergeList(Node head1, Node head2) {
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;

        Node dummy = new Node(-1);
        Node curr = dummy;
        Node ptr1 = head1;
        Node ptr2 = head2;
        while (ptr1 != null && ptr2 != null) {
            if (ptr1.data < ptr2.data) {
                curr.bottom = ptr1;
                ptr1 = ptr1.bottom;

            } else {
                curr.bottom = ptr2;
                ptr2 = ptr2.bottom;
            }
            curr = curr.bottom;
        }
        if (ptr1 != null)
            curr.bottom = ptr1;
        else
            curr.bottom = ptr2;

        return dummy.bottom;
    }
}

Was this solution helpful?