[LeetCode] Merge Two Sorted Lists

Problem: 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:

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

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

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

Approach: We have already done it recursively before. Just adding the iterative approach here. You can just understand it by looking at the implementation.

Implementation in C#:

    public ListNode MergeTwoLists(ListNode list1, ListNode list2)

    {

        var itr1 = list1;

        var itr2 = list2;

        var head = new ListNode();

        var itr = head;

        while (itr1 != null && itr2 != null)

        {

            if (itr1.val <= itr2.val)

            {

                itr.next = itr1;

                itr1 = itr1.next;

            }

            else

            {

                itr.next = itr2;

                itr2 = itr2.next;

            }

            itr = itr.next;

        }

        if (itr1 != null)

        {

            itr.next = itr1;

        }

        else if (itr2 != null)

        {

            itr.next = itr2;

        }

        return head.next;

    }

Complexity: O(Max(m, n))