题目：

将两个排序链表合并为一个新的排序链表

 样例

给出 1->3->8->11->15->null，2->null，

返回 1->2->3->8->11->15->null。

解题：

数据结构中的书上说过，可解，异步的方式移动两个链表的指针，时间复杂度O(n+m)

Java程序：

/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param ListNode l1 is the head of the linked list     * @param ListNode l2 is the head of the linked list     * @return: ListNode head of linked list     */    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        // write your code here        if(l1==null && l2!=null)            return l2;        if(l1!=null && l2==null)            return l1;        if(l1==null && l2==null)            return null;        ListNode head = new ListNode(0);        ListNode current = head;                      while(l1!=null && l2!=null){                if(l1.val<=l2.val){                    current.next = l1;                    current = current.next;                    l1 = l1.next;                }else{                    current.next = l2;                    current = current.next;                    l2 = l2.next;                }            }        if(l1!=null)            current.next= l1;        if(l2!=null)            current.next=l2;        return head.next;    }}

总耗时: 13348 ms

Python程序：

"""Definition of ListNodeclass ListNode(object):    def __init__(self, val, next=None):        self.val = val        self.next = next"""class Solution:    """    @param two ListNodes    @return a ListNode    """    def mergeTwoLists(self, l1, l2):        # write your code here        if l1==None:            return l2        if l2==None:            return l1        if l1==None and l2==None:            return None        head = ListNode(0)        p = head        while l1!=None and l2!=None:            if l1!=None and l2!=None:                if l1.val<= l2.val:                    p.next = l1                    p = p.next                    l1 = l1.next                else:                    p.next = l2                    p = p.next                    l2 = l2.next            if l1==None:                p.next = l2                break            if l2==None:                p.next = l1                break        return head.next

总耗时: 2032 ms

 参考剑指OfferP117

利用递归的思想

小的节点链接，下一次递归

递归的好处是不用单独搞个节点当作头节点了，通俗点说是许多头节点连接起来的，最终我们返回的是第一个头节点

/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param ListNode l1 is the head of the linked list     * @param ListNode l2 is the head of the linked list     * @return: ListNode head of linked list     */    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        // write your code here        if(l1==null && l2!=null)            return l2;        if(l1!=null && l2==null)            return l1;        if(l1==null && l2==null)            return null;        ListNode MergeHead = null;        if(l1.val < l2.val){            MergeHead = l1;            MergeHead.next = mergeTwoLists(l1.next,l2);        }else{            MergeHead = l2;            MergeHead.next = mergeTwoLists(l1,l2.next);        }        return MergeHead;            }}

总耗时: 14047 ms

"""Definition of ListNodeclass ListNode(object):    def __init__(self, val, next=None):        self.val = val        self.next = next"""class Solution:    """    @param two ListNodes    @return a ListNode    """    def mergeTwoLists(self, l1, l2):        # write your code here        if l1==None:            return l2        if l2==None:            return l1        if l1==None and l2==None:            return None        head = None        if l1.val< l2.val:            head = l1            head.next = self.mergeTwoLists(l1.next,l2)        else:            head = l2            head.next = self.mergeTwoLists(l1,l2.next)        return head

总耗时: 2403 ms