namespace LeetCode.Logic;

public class LinkedListMerger
{
    /// <summary>
    /// Merges two sorted linked lists into one sorted linked list.
    /// Time Complexity: O(n + m) where n and m are lengths of the lists.
    /// Space Complexity: O(1) as we are reusing existing nodes.
    /// </summary>
    public ListNode? MergeTwoLists(ListNode? list1, ListNode? list2)
    {
        // Use a dummy node to act as the starting point
        ListNode dummy = new ListNode(-1);
        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;
        }

        // If one list is longer, attach the remainder
        current.next = list1 ?? list2;

        return dummy.next;
    }
}

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