题目：
将两个排序链表合并为一个新的排序链表
样例
给出 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 ListNode
class 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; }
}
Java Code
总耗时: 14047 ms
"""
Definition of ListNode
class 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
Python Code
总耗时: 2403 ms