DAY 55: Mastering Linked List Problems – Merge K Lists, Flatten, Clone a List with Random Pointers & Browser History | Linked List

---

🚀 Introduction

Welcome to Day 55 of my DSA Journey!
After spending an intense few weeks mastering Recursion, I’ve now shifted my focus to one of the most fundamental data structures in DSA — the Linked List.

Transitioning from recursion to linked lists has been both challenging and rewarding, as these concepts are closely related, especially when solving problems that involve traversal and pointer manipulation.

Over the past 3 days, I’ve practiced several key problems on Linked Lists, including: Merge K Sorted Lists, Flatten a Linked List, Clone a Linked List with Random and Next Pointers, and Design Browser History.

I’m documenting this journey publicly to stay consistent, track my progress, and hopefully help others who are starting their DSA journey from scratch.

👉 Feel free to follow me on Twitter for real-time updates, problem breakdowns, and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 52

• Merge K Sorted Lists
• Flatten a Linked List

Day 53

• Clone a Linked List with Random and Next Pointers

Day 54

• Design Browser History (using Doubly Linked List)

Now, let’s dive deeper into each of these problems 👇

---

Q 1. Merge K Sorted Lists

Given an array (or list) of k linked lists, where each linked list is already sorted in ascending order.
Our goal is to merge all these lists into one sorted linked list and return its head.

Example:

Input:
k = 3
List 1 : 1 → 4 → 5
List 2 : 1 → 3 → 4
List 3 : 2 → 6

Output:
1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

We take three individually sorted lists and merge them into one single sorted linked list, preserving the order.

Approach:

In this implementation, we use a pairwise merge approach:

1. Start with the first linked list as mergedHead.
2. Iteratively merge mergedHead with the next list from the array.
3. Continue until all k lists are merged into one.
4. To merge two sorted linked lists, we use the classic merge technique (like merging two arrays in merge sort).

Code Implementation:

private static Node mergeKSortedLists(ArrayList<Node> list) {
    Node mergedHead = null;

    // Iteratively merge one list at a time
    for (int i = 0; i < list.size(); i++) {
        Node tempHead = list.get(i);
        mergedHead = merge(mergedHead, tempHead);
    }

    return mergedHead;
}

// Helper function to merge two sorted linked lists
private static Node merge(Node list1, Node list2) {
    Node dummy = new Node(-1);
    Node temp = dummy;

    while (list1 != null && list2 != null) {
        if (list1.value <= list2.value) {
            temp.next = list1;
            list1 = list1.next;
        } else {
            temp.next = list2;
            list2 = list2.next;
        }
        temp = temp.next;
    }

    // Append remaining nodes
    if (list1 != null) {
        temp.next = list1;
    } else {
        temp.next = list2;
    }

    return dummy.next;
}

Time & Space Complexity:

• Merging Two Lists: O(n + m) where n and m are the lengths of the two lists.

• Merging K Lists Iteratively: If total nodes = N, then worst-case complexity → O(k * N)

  • Because for each new list, we merge it with the already merged result.

• Space Complexity:

  • O(1) (No extra space except dummy node; merging is done in-place).

Note: While this solution works fine for small values of k, it becomes less efficient when k is large.

Optimized approaches include:

• Min Heap / Priority Queue → O(N log k)
• Divide and Conquer Merge → O(N log k)

Final Thoughts:

• This approach is simple, easy to understand, and works well for small k.
• For interview purposes, always mention the optimized heap-based approach for large k.
• This problem builds a strong foundation for solving advanced linked list problems such as Merge K Sorted Arrays or External Sorting.

Key takeaway: Start with a simple iterative merge, then scale up to priority queues for efficiency.

---

Q 2. Flatten a Linked List

Given a Linked List of Linked Lists, where each node has:

• A next pointer → points to the next node in the main list.
• A child pointer → points to a sorted linked list.

The task is to flatten the list into a single sorted linked list using the child pointer.

Example:

Input:

Head → 5 → 10 → 19 → 28  
        |      |      |  
        V      V      V  
        7      20     22 → 50  
        |             |  
        V             V  
        8             35  
        |             |  
        V             V  
        30            40

Output:
5 → 7 → 8 → 10 → 19 → 20 → 22 → 28 → 30 → 35 → 40 → 50

Here, the list has been flattened into a single sorted list using only the child pointers.

Approach:

We solve this problem using a combination of recursion and merging sorted linked lists:

1. Base Case

   • If the head is null or there’s only one node left (i.e., head.next == null), there’s nothing to flatten.
   • In this case, simply return the head.

2. Recursive Step

   • Recursively call the function for head.next.
   • This will flatten the list starting from the next node onward, ensuring that when recursion unwinds, we already have a flattened list for the right side.

3. Merge Current with Flattened

   • Now, merge the current node’s child list (head.child) with the already flattened list from step 2.
   • We use a helper function (mergeTwoSortedList) which works just like merging in merge sort.
   • During the merge, always pick the smaller node first and link it through the child pointer.

4. Remove Next Pointers

   • Since the final flattened list should be single-level (connected only via child pointers), set all next pointers to null during merging.

5. Return the Merged List

   • After recursion and merging complete, the returned head points to a fully flattened, sorted linked list.

The key idea is:

• Break the problem into smaller parts by recursion.
• Solve one part (flatten right side), then combine (merge) with the current part.
• This divide-and-conquer approach ensures a clean and simple solution.

Code Implementation:

private Node flattenList(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    // Recursively flatten the rest of the list
    Node mergedHead = flattenList(head.next);

    // Merge current list with flattened result
    return mergeTwoSortedList(head, mergedHead);
}

private Node mergeTwoSortedList(Node list1, Node list2) {
    Node dummy = new Node(-1);
    Node temp = dummy;

    while (list1 != null && list2 != null) {
        if (list1.data <= list2.data) {
            temp.child = list1;
            list1 = list1.child;
        } else {
            temp.child = list2;
            list2 = list2.child;
        }
        temp = temp.child;
        temp.next = null; // ensure 'next' is null
    }

    // Attach the remaining nodes
    if (list1 != null) {
        temp.child = list1;
    } else {
        temp.child = list2;
    }

    return dummy.child;
}

Time & Space Complexity:

• Merging Two Lists: O(n + m), where n and m are the lengths of the two lists.
• Flattening K Lists: If there are N total nodes across all lists, worst-case complexity → O(N * k), where k = number of lists.
• Space Complexity: O(1) (merging is done in-place, excluding recursion stack).

Note: For large k, this solution is less efficient. Optimized approaches include:

• Min Heap / Priority Queue: O(N log k)
• Divide & Conquer Merge: O(N log k)

Final Thoughts:

• The recursive + merge approach is intuitive and excellent for conceptual understanding.
• In interviews, always mention the priority queue method for better scalability.
• This problem strengthens your skills in recursion, merging, and linked list manipulations.

Key Takeaway: Focus on reducing merge operations using heaps or divide & conquer for large input sizes.

---

Q 3. Clone a Linked List with Random and Next Pointers

We are given a special linked list where each node has two pointers:

1. next → points to the next node in the list.
2. random → points to any node in the list (or null).

The task is to create a deep copy (clone) of this linked list.

• The new list should have entirely new nodes.
• Both next and random pointers must be set correctly.

Example:

Input List:

1 → 2 → 3 → 4 → 5
|    |    |      
V    V    V      
3    1    5

• Here, each vertical arrow (V) represents a random pointer.
  • Node 1 → random points to Node 3
  • Node 2 → random points to Node 1
  • Node 3 → random points to Node 5
  • Nodes 4 and 5 → random is null

Cloned Output List:

1' → 2' → 3' → 4' → 5'
|     |     |      
V     V     V      
3'    1'    5'

Notice:

• The cloned list has all new nodes (1', 2', 3', etc.).
• Random connections are preserved but point to cloned nodes instead of the original ones.

Approach:

We solve this in 3 main steps:

1. Clone nodes and insert them in between

• Traverse the original list.
• For each node temp, create a clone copyNode and insert it right after temp.

Example after step 1:
1 → 1' → 2 → 2' → 3 → 3' → ...

2. Copy random pointers

• Traverse again.
• If temp.random != null, set:

  temp.next.random = temp.random.next
  

• This works because temp.next is the clone, and temp.random.next is the clone of the random node.

3. Separate cloned list from original

• Traverse again and detach cloned nodes (1', 2', etc.) into a new list.
• Restore the original list’s next pointers.

Code Implementation:

private static Node copyRandomList(Node head) {
  // Step 1: Insert cloned nodes after originals
  Node temp = head;
  while (temp != null) {
      Node copyNode = new Node(temp.value);
      copyNode.next = temp.next;
      temp.next = copyNode;

      temp = temp.next.next;
  }

  // Step 2: Connect random pointers
  temp = head;
  while (temp != null) {
      Node copyNode = temp.next;
      if (temp.random == null) {
          copyNode.random = null;
      } else {
          copyNode.random = temp.random.next;
      }
      temp = temp.next.next;
  }

  // Step 3: Detach cloned list
  temp = head;
  Node dummy = new Node(-1);
  Node res = dummy;
  while (temp != null) {
      res.next = temp.next;       // add cloned node
      temp.next = temp.next.next; // restore original link

      res = res.next;
      temp = temp.next;
  }

  return dummy.next;
}

Time & Space Complexity:

• Step 1 (Insert clones): O(N)
• Step 2 (Copy random pointers): O(N)
• Step 3 (Detach clone list): O(N)

Total Time Complexity: O(N)

• Space Complexity:
  • O(1) extra (since we’re not using a HashMap, only dummy nodes and pointers).
  • The cloned list itself requires new memory for N nodes, but no extra auxiliary space.

Final Thoughts:

• This is the optimal solution because it avoids using a HashMap<Node, Node> (which costs O(N) space).
• The trick is interweaving cloned nodes with the original ones to reuse their random relationships.
• In interviews, you should first mention the HashMap approach (easy to explain), then move to this O(1) space approach for optimization.

Key Takeaway: Always look for ways to avoid extra space by cleverly reusing existing structures.

---

Q 4. Design Browser History

We need to design a browser history system that mimics the behavior of real browsers.

The system should support three main operations:

1. Visit a URL → Navigate to a new webpage.
2. Back(steps) → Go back up to steps pages in history.
3. Forward(steps) → Go forward up to steps pages in history.

Example:

Operations:

BrowserHistory("leetcode.com");
visit("google.com");
visit("facebook.com");
visit("youtube.com");
back(1);
back(1);
forward(1);
visit("linkedin.com");
forward(2);
back(2);
back(7);

Output:

null
null
null
null
"facebook.com"
"google.com"
"facebook.com"
null
"linkedin.com"
"google.com"
"leetcode.com"

Approach:

We use a Doubly Linked List to represent the browser history.

• Each node stores a url.
• Each node has two pointers:
  • prev → points to the previous page.
  • next → points to the next page.
• A curr pointer keeps track of the current page.

Operations:

1. Visit(url):

   • Create a new node for the URL.
   • Discard all forward history (curr.next = null).
   • Link the new node after curr.
   • Move curr to the new node.

2. Back(steps):

   • Move curr backward up to steps times using prev.
   • Stop if prev == null.
   • Return the current URL.

3. Forward(steps):

   • Move curr forward up to steps times using next.
   • Stop if next == null.
   • Return the current URL.

Code Implementation:

public class BrowserHistory {
    private Node curr;

    // Doubly Linked List Node
    private static class Node {
        String url;
        Node next;
        Node prev;

        public Node(String url) {
            this.url = url;
        }
    }

    // Initialize with homepage
    public BrowserHistory(String homepage) {
        curr = new Node(homepage);
    }

    // Visit a new page
    public void visit(String url) {
        curr.next = null; // clear forward history

        Node node = new Node(url);
        node.prev = curr;
        curr.next = node;
        curr = node;
    }

    // Move back in history
    public String back(int steps) {
        while (steps != 0) {
            if (curr.prev == null) break;
            curr = curr.prev;
            steps--;
        }
        return curr.url;
    }

    // Move forward in history
    public String forward(int steps) {
        while (steps != 0) {
            if (curr.next == null) break;
            curr = curr.next;
            steps--;
        }
        return curr.url;
    }
}

Time & Space Complexity:

• Visit: O(1)
• Back(steps): O(steps) (worst case traverse steps times)
• Forward(steps): O(steps) (worst case traverse steps times)

Overall: Efficient enough since each operation is linear in the number of steps requested.

• Space Complexity: O(N) → we store each visited page as a node in the doubly linked list.

Final Thoughts:

• This is a clean, object-oriented design that mimics real-world browser navigation.
• Using a Doubly Linked List allows us to move both backward and forward efficiently.
• In interviews, we can also mention alternative approaches:
  • Two Stacks Approach (Back stack + Forward stack).
  • ArrayList with pointer (simpler but less flexible for very large histories).

Key Takeaway: Use a doubly linked list when we need efficient bidirectional navigation in data structures.

---

5. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

6. Conclusion:

In this blog, we explored some of the most important Linked List problems that frequently appear in coding interviews and real-world applications:

• ✅ Merge K Sorted Lists – building a foundation for advanced merging techniques.
• ✅ Flatten a Linked List – strengthening recursion and divide & conquer intuition.
• ✅ Clone a Linked List with Random Pointers – mastering deep copy techniques with pointers.
• ✅ Design Browser History – applying linked lists to simulate real-world systems.

Each of these problems not only sharpens mine understanding of linked list manipulation but also helps me to think about optimization trade-offs (e.g., iterative vs. heap-based merging, recursion vs. in-place solutions, doubly linked lists vs. stacks).

💡 Key Takeaway: Mastering Linked Lists is not about memorizing solutions — it’s about understanding how to navigate, manipulate, and optimize pointer-based structures. Once we’re comfortable, we’ll find it much easier to tackle trees, graphs, and even advanced system design problems.

👉 If you’re on a similar journey, stay consistent, code daily, and don’t shy away from challenging problems. Every step makes you a better problem solver.

Thanks for reading! 🙌
Follow me here (and on Twitter) for more updates as I continue my DSA journey 🚀.