剑指offer-16-合并有序链表

思路

• 建立一个链表头指针，把两个输入链表剥离下来放到新链表之后
• 直接合并，把链表list2中的元素插入到链表list1中
  其中两种思路基本一致，因为结果中并不包含思路一的头指针，可以把头指针设置为list1和list2的较小者，然后转化为思路1

  代码

  public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode h=new ListNode(0);
        ListNode p=h,l1=list1,l2=list2;
        while(l1!=null || l2!=null){
            if(l1==null){
                p.next=l2;
                l2=l2.next;
            }else if(l2==null){
                p.next=l1;
                l1=l1.next;
            }else{
                if(l1.val<=l2.val){
                    p.next=l1;
                    l1=l1.next;
                }else{
                    p.next=l2;
                    l2=l2.next;
                }
            }
            p=p.next;
        }
        return h.next;
    }
  }