21. Merge Two Sorted Lists

题目：

合并两个已排序的链表，并将其作为一个新列表返回。新列表应该通过拼接前两个列表的节点来完成。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路：

1. 判断l1和l2是否存在空链表，两个都空返回null，有一个空链表就直接返回另个链表；
2. 找出l1和l2中最小的节点，作为新链表的头结点；
3. 然后依次比较l1和l2，将较小的节点插入到新的链表后面；

解答：

class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null&&l2==null) return null;
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode newhead = null;
        ListNode p1= l1;
        ListNode p2= l2;
        if(l1.val<l2.val){
            newhead = l1;
            p1=p1.next;
        }else {
            newhead =l2;
            p2=p2.next;
        }
        ListNode p = newhead;
        while(p1!=null && p2!=null){
            if(p1.val<p2.val){
                p.next = p1;
                p= p.next;
                p1=p1.next;
            }else{
                p.next = p2;
                p= p.next;
                p2=p2.next;
            }
        }
        if(p1==null&&p2==null){
            return newhead;
        }
        else if(p1==null&&p2!=null){
            p.next = p2;
        }else if(p2==null&&p1!=null){
            p.next = p1;
        }
        return newhead;
    }
}