# 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;
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://private-26.gitbook.io/notes/coding/misc/flatten-a-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.