Merge Two Sorted Linked Lists": An In-Place Iterative Approach

Hello everyone! Today, we're diving into a cornerstone linked list problem: "Merge Two Sorted Linked Lists" (LeetCode #21).

Given the heads of two sorted linked lists, our goal is to merge them into a single sorted linked list by re-linking their nodes. While a common approach uses a dummy node to build a new list, my solution explores an efficient in-place iterative method that directly modifies the existing lists. Let's master the art of pointer management!

---

Understanding the Problem:

You are provided with two linked lists, list1 and list2, both of which are already sorted in non-decreasing order. Your task is to combine all their nodes into a single new linked list that is also sorted. The new list should be formed by taking nodes from the original lists, not creating new ones (hence, "in-place" merging). You must return the head of this newly merged list.

Examples:

• Example 1:

  • list1 = [1, 2, 4]

  • list2 = [1, 3, 5]

  • Output: [1, 1, 2, 3, 4, 5]

• Example 2:

  • list1 = []

  • list2 = [1, 2]

  • Output: [1, 2] (Handling empty lists is important!)

---

My Thought Process & Approach (Iterative In-Place Merging):

When merging two sorted lists, the core idea is to always pick the smaller value from the current heads of the two lists and append it to our new merged list. We continue this process until one list is exhausted, then append the remaining nodes of the other list.

My approach implements this iteratively, specifically aiming for an in-place merge without using a separate dummy node to build the new list. This means we'll be re-pointing the next pointers of the existing nodes.

Algorithm Steps:

1. Handle Base Cases:

   • If both list1 and list2 are null, the result is null.

   • If list1 is null, list2 is the merged list.

   • If list2 is null, list1 is the merged list.

2. Determine Initial Head (P):

   • We need to decide which list's head will be the head of our final merged list. This will be the node with the smaller value between list1.val and list2.val.

   • Let's call the list starting with the smaller value prim (primary list) and the other sec (secondary list).

   • Store prim's initial head in a ListNode P; this P will be returned at the end.

3. Iterative Weaving (Main Loop):

   • We'll iterate as long as both prim and sec have nodes.

   • Inner Loop (Finding Insertion Point): We advance prim forward until we find the correct spot to insert the current sec node. This means prim.next should either be null (end of prim's current segment) or prim.next.val should be greater than sec.val. Java

       while(prim.next != null && prim.next.val <= sec.val){
           prim = prim.next;
       }
     

     Perform Insertion: Once the inner loop finishes, prim is now at the node before where sec should be inserted.

     • First, save the next node of sec because sec's next pointer will be modified. ListNode temp = sec.next;

     • Then, point the current sec node's next to where prim's next was: sec.next = prim.next;

     • Now, link prim to sec: prim.next = sec;

     • Advance sec to its next node (the one we saved in temp): sec = temp;

     • Finally, advance prim to the node it just inserted (the old sec). This is important so prim continues its traversal from the newly integrated part of the list: prim = prim.next;

4. Append Remaining Nodes:

   • After the main while loop, one of the lists (prim or sec) has become null.

   • If sec still has remaining nodes (meaning prim was exhausted first), we simply append the rest of sec to the end of prim's current position: prim.next = sec; (Note: prim's current position is the last node added to the merged list).

This approach requires very careful pointer management but successfully merges the lists in-place.

---

Java Code Implementation:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if(list1 == null && list2 == null){
            return null;
        }
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode prim;
        ListNode sec;
        if(list1.val<list2.val){
            prim = list1;
            sec = list2;
        }
        else{
            prim = list2;
            sec = list1;
        }
        ListNode P = prim;
        while(prim!=null && sec!= null){
            while(prim.next!=null && prim.next.val<=sec.val){
                prim = prim.next;
            }
            ListNode temp = sec;
            temp = temp.next;
            sec.next = prim.next;
            prim.next = sec;
            sec = temp;
            prim = prim.next;
        }
        if(sec!=null){
            prim.next = sec;
        }
        return P;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(M + N)

  • Where M is the number of nodes in list1 and N is the number of nodes in list2.

  • In the worst case, we traverse each node of both lists exactly once. Each node is compared, and its pointers are adjusted a constant number of times.

  • Therefore, the total time complexity is linear with respect to the total number of nodes in both lists.

• Space Complexity: O(1)

  • The algorithm modifies the next pointers of the existing nodes directly.

  • It only uses a few fixed-size pointers (prim, sec, P, temp).

  • No auxiliary data structures are created whose size depends on the input list lengths.

  • This makes it an extremely space-efficient in-place solution.