Lintcode - Merge Two Sorted Lists

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

Example

Given1->3->8->11->15->null,2->null, return1->2->3->8->11->15->null.

Analysis

The key point of this question is have a dummyhead node with max value assigned to it. This way, we can use l1.next node to compare with the l2 current node.

Solution

   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }

        if (l2 == null){
            return l1;
        }

        ListNode dummy = new ListNode(Integer.MAX_VALUE);
        dummy.next = l1;
        l1 = dummy;

        ListNode next = null;
        do {
            while (l1.next != null && l1.next.val < l2.val){ 
                l1 = l1.next;
            }

            next = l2.next;
            append(l1, l2);
            l2 = next;
        } while (l2 != null);

        return dummy.next;
    }

    public void append(ListNode l1, ListNode l2){
        ListNode temp = l1.next;
        l1.next = l2;
        l2.next = temp;
    }