daniel.baird
10/8/2018 - 4:30 AM

Merge Two Sorted Lists

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.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    // if we have nothing to merge, just go ahead and return.
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    
    ListNode head;
    ListNode tail;
    
    // Pick a node to be our new head.
    if (l1.val <= l2.val) {
        head = l1;
        l1 = head.next;
    } else {
        head = l2;
        l2 = head.next;
    }
    
    head.next = null;
    tail = head;
    
    // While there are items that rquire merging
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            tail = tail.next;
            l1 = l1.next;
        } else {
           tail.next = l2;
            tail = tail.next;
            l2 = l2.next; 
        }
    }
    
    // At this point , at least one of the lists is empty
    if (l1 != null) {
        tail.next = l1;
    } else if (l2 != null) {
        tail.next = l2;
    }
    
    return head;
}