《剑指Offer》16合并两个排序的链表

题目：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

递归的方法：

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {         if(list1==null) {             return list2;         }else if(list2==null) {             return list1;         }         ListNode pMergeHead=null;         if(list1.val<list2.val){              pMergeHead=list1;              pMergeHead.next=Merge(list1.next,list2);         }else {             pMergeHead=list2;             pMergeHead.next=Merge(list1,list2.next);         }
        return pMergeHead;
    }
}

非递归的方法，递归和非递归的方法时间复杂度都是O(n)。

class ListNode {     int val;     ListNode next;     ListNode(int val) {         this.val=val;     }
}
public class Solution {     public ListNode Merge(ListNode list1,ListNode list2) {         if(list1==null) {
            return list2;
        }else if(list2==null) {
            return list1;
        }
        ListNode pMergeHead=null;
        ListNode pCur=null;
        ListNode p1=list1;
        ListNode p2=list2;
        if (p1.val<p2.val) {
            pMergeHead=p1;
            pCur=pMergeHead;
            p1=p1.next;
        }else {
            pMergeHead=p2;
            pCur=pMergeHead;
            p2=p2.next;
        }
        while(p1!=null&&p2!=null) {
            if (p1.val<p2.val) {
                pCur.next=p1;
                pCur=p1;
                p1=p1.next;
            }else {
                pCur.next=p2;
                pCur=p2;
                p2=p2.next;
            }
        }
        if (p1!=null) {
            pCur.next=p1;
        }else {
            pCur.next=p2;
        }
        return pMergeHead;     }
}