2. Merge Two Sorted Lists

Description

Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Approach 1: Brute Force (Extract, Sort, Rebuild)

Intuition: Dump all node values from both lists into a dynamic array, sort the array using standard sorting, and construct a brand-new linked list from the sorted values.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> values = new ArrayList<>();
    
    // 1. Extract values into an array
    while (list1 != null) {
        values.add(list1.val);
        list1 = list1.next;
    }
    while (list2 != null) {
        values.add(list2.val);
        list2 = list2.next;
    }
    
    // 2. Sort the array
    Collections.sort(values);
    
    // 3. Rebuild the merged linked list
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    for (int val : values) {
        current.next = new ListNode(val);
        current = current.next;
    }
    
    return dummy.next;
}

• Time Complexity: $O(N\log N)$ where $N$ is the total number of nodes (due to array sorting).
• Space Complexity: $O(N)$ extra space to store array elements and create new list nodes.

Approach 2: Optimal (Two-Pointer Zipper Method)

• Create dummy node to get the loop to start
• Check for smaller one and adjust next pointer and after loop is done there is possible one of the list still not fully iterated so add it to the last node after the loop
• Time: O(m + n) Space: O(1)

/**
 * 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) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
 
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
		// can use this as well
		// current.next = (list1 != null) ? list1 : list2;
        if (list1 != null)
            curr.next = list1;
        if (list2 != null)
            curr.next = list2;
 
        return dummy.next;        
    }
}

Intuition: Think of two sorted lines of people. Compare the person at the front of each line, stitch the smaller person to your merged list, and advance that list’s pointer. Using a dummy node avoids writing special edge-case logic for the start of the list.

• Time Complexity: $O(N+M)$ — single pass through both lists.
• Space Complexity: $O(1)$ — modifies existing node pointers in place without extra memory.

Memory Hooks for Interviews

• The Dummy Node Trick: Whenever building or modifying a linked list head dynamically, start with dummy = new ListNode(-1) and return dummy.next.
• The Zipper Action: Compare heads $\to$ attach smaller node $\to$ move forward $\to$ attach leftover tail at the end.