Merge Two Sorted Lists easy

Problem Statement

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1

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

Example 2

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

Steps

1. Handle Empty Lists: If either list1 or list2 is null (empty), return the other list.
2. Create a Dummy Node: Create a dummy node to simplify the process of building the merged list. This dummy node will point to the head of the merged list.
3. Initialize Pointers: Use pointers tail (initially pointing to the dummy node) and p1, p2 (pointing to the heads of list1 and list2 respectively).
4. Iterate and Compare: While p1 and p2 are not null, compare the values at p1 and p2.
   • Append the smaller node to tail. Move tail and the corresponding pointer (p1 or p2) forward.
5. Handle Remaining Nodes: After one list is exhausted, append the remaining nodes from the other list to tail.
6. Return the Merged List: Return the next node after the dummy node (which is the head of the merged list).

Explanation

The algorithm efficiently merges two sorted lists by iteratively comparing the heads of the remaining portions of each list. The use of a dummy node eliminates edge cases and simplifies the code by always having a valid tail to append to. The time complexity is linear because we visit each node in both lists exactly once.

Code

/**
 * 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) {
        // Handle empty lists
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        // Create a dummy node
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // Initialize pointers
        ListNode p1 = list1;
        ListNode p2 = list2;

        // Iterate and compare
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                tail.next = p1;
                p1 = p1.next;
            } else {
                tail.next = p2;
                p2 = p2.next;
            }
            tail = tail.next;
        }

        // Handle remaining nodes
        tail.next = (p1 != null) ? p1 : p2;

        // Return the merged list
        return dummy.next;
    }
}

Complexity

• Time Complexity: O(m + n), where 'm' and 'n' are the lengths of list1 and list2 respectively. We iterate through each list once.
• Space Complexity: O(1). We use a constant amount of extra space regardless of the input size. The space used by the merged list itself is not considered in space complexity analysis.