【剑指 offer】合并链表

描述：

输入两个递增的链表，单个链表的长度为 n，合并这两个链表并使新链表中的节点仍然是递增排序的。

思路：

public class Solution {
    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;

    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;

    while(head1 != null && head2 != null){
        if(head1.val < head2.val){
            tmp.next = head1;
            tmp = tmp.next;
            head1 = head1.next;
        }else {
            tmp.next = head2;
            tmp = tmp.next;
            head2 = head2.next;
        }
    }
    if(head1 != null){
        tmp.next = head1;
    }
    if(head2 != null){
        tmp.next = head2;
    }
    return newHead.next;
    }
}