logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
Calculate Floor & CeilingFind Nth Root Of MFlatten A Linked ListImplement Lower BoundImplement Upper BoundNumber of occurrence
Code Scratch/leetcode/misc

Flatten A Linked List

2 min read
On this pageIntuition
IntuitionComplexityCode

# 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 ComplexityTime Complexity
O(1)\text{O}(1)O(1)O(N∗log⁡N)\text{O}(N*\log{N})O(N∗logN)

# Code

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;
}
 
←PreviousFind Nth Root Of MNext→Implement Lower Bound

On this page

IntuitionComplexityCode