Merge Two Sorted Lists

Problem

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

Solution

Recursive Solution: O(n) time, O(n) space

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

Iterative Solution: O(n) time, O(1) space

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode dummy = new ListNode(0), cur = dummy; //To return the new head, we must have a reference to it
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }  
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next; //node 
        }
        if (l1 == null) cur.next = l2;
        if (l2 == null) cur.next = l1;
        return dummy.next;
    }
}

Analysis

In the iterative solution
We use dummy to keep a reference to the head of list and cur to mark current sorted list
We set cur.next depending on the value of two nodes and move forward smaller node
Meanwhile, we need to move forward the cur node as well
After the while loop, we simply set the rest of list in case one of the node is not empty yet

In the typical recursive solution
We traversal two linked lists and return smaller ListNode after recursively setting its next
Notice how we avoid null by using the first two if statements