C# LeetCode 21: Merge Two Sorted Lists

Problem:

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.

Code:

public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

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

        // Attach the remaining nodes
        current.next = list1 ?? list2;

        return dummy.next;
    }

Approach

We can merge two sorted lists using a two-pointer technique:

1.Use a dummy head node

• Acts as a placeholder so we can easily return the head later.
• current will always point to the last node of the merged list.

2.Iterate while both lists are non-empty

• Compare the current nodes of list1 and list2.
• Append the smaller node to the merged list.
• Advance the pointer in whichever list we took the node from.
• Move current forward to the newly added node.

3. Attach the remainder

• Once one list is empty, attach the remaining nodes of the other list.
• Since both input lists are sorted, the remaining part is already in order.

4. Return the merged list
The merged list starts at dummy.next (skip the placeholder node).

So we'd have something that looks like this:

dummy → 0
current → 0
list1 → 1 → 3 → 5
list2 → 2 → 4 → 6

# Iteration 1
dummy → 0 → 1
current → 1
list1 → 3 → 5
list2 → 2 → 4 → 6


# Iteration 2
dummy → 0 → 1 → 2
current → 2
list1 → 3 → 5
list2 → 4 → 6

# Iteration 3
dummy → 0 → 1 → 2 → 3
current → 3
list1 → 5
list2 → 4 → 6

# Iteration 4
dummy → 0 → 1 → 2 → 3 → 4
current → 4
list1 → 5
list2 → 6

# Iteration 5
dummy → 0 → 1 → 2 → 3 → 4 → 5
current → 5
list1 → null
list2 → 6


# Finally Append Remaining
dummy → 0 → 1 → 2 → 3 → 4 → 5 → 6

# result (dummy.next)
1 → 2 → 3 → 4 → 5 → 6

Hope this was helpful, as always drop me a follow here, or on x (twitter)