> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/misc/flatten-a-linked-list.md).

# Flatten A Linked List

## Intuition

Each node in the linked list has:

* A `next` pointer to another node (head of another sorted list).
* A `child` pointer to a **sorted** linked list.

Since every list is already sorted, we can leverage a **min-heap (priority queue)** to always pick the node with the smallest value among all available nodes and build a final **flattened sorted list**.

## Complexity

| Space Complexity | Time Complexity          |
| ---------------- | ------------------------ |
| $$\text{O}(1)$$  | $$\text{O}(N\*\log{N})$$ |

## Code

```java
public static Node flattenLinkedList(Node mainHead) {
    // Dummy node to build the result list
    Node dummyNode = new Node(-1);
    Node flattenedTail = dummyNode;

    // Min-heap to get the smallest node at each step
    PriorityQueue<Node> minHeap = new PriorityQueue<Node>((a, b) -> Integer.compare(a.data, b.data));

    // Push all head nodes (connected via next) into the heap
    while (mainHead != null) {
        Node nextHead = mainHead.next;
        mainHead.next = null; // disconnect to avoid interference
        minHeap.add(mainHead);
        mainHead = nextHead;
    }

    // Process nodes in heap
    while (!minHeap.isEmpty()) {
        // Extract the node with the smallest value
        Node currentMinNode = minHeap.remove();
        Node childNode = currentMinNode.child;
        currentMinNode.child = null;

        // If the node has a child, add it to the heap
        if (childNode != null) {
            minHeap.add(childNode);
        }

        // Add current node to the flattened list
        flattenedTail.child = currentMinNode;
        flattenedTail = currentMinNode;
    }

    // Return the flattened list starting after dummy node
    return dummyNode.child;
}

```