Merge Two Sorted Lists easy

Problem Statement

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

Example 1

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

Example 2

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

Example 3

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

Steps

1. Handle Empty Lists: Check if either list1 or list2 is null (empty). If so, return the non-empty list or null if both are empty.

2. Create a Dummy Node: Create a dummy node to simplify the head insertion logic. This dummy node will point to the head of the merged list.

3. Iterative Merge: Use two pointers, p1 and p2, to iterate through list1 and list2 respectively. Compare the values at p1 and p2. The smaller value's node is appended to the merged list (pointed to by tail). Then move the pointer of the appended node forward.

4. Handle Remaining Nodes: After one of the lists is exhausted, append the remaining nodes of the other list to the merged list.

5. Return the Merged List: Return the next node after the dummy node (which is the actual head of the merged list).

Explanation

The algorithm uses an iterative approach to efficiently merge the two sorted lists. By using a dummy node, we avoid special handling for the head of the merged list. The comparison and appending process ensures that the resulting list remains sorted. The time complexity is linear because we visit each node in both lists once. The space complexity is constant because we use a fixed number of variables regardless of the input size.

Code

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public 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();
        ListNode tail = dummy;

        // Iterate and merge
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        // Append remaining nodes
        tail.next = list1 ?? list2;

        // 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 traverse 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 output list is not considered in space complexity analysis for this problem.