题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路：
首先最直观的做法就是取出每一个节点元素，排序后重新生成链表。
方法一：
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res_temp=[]
while l1:
res_temp.append(l1.val)
l1 = l1.next
while l2:
res_temp.append(l2.val)
l2 =l2.next
res_temp.sort()
res = ListNode(0)
tmp = res #用来移动节点
for i in xrange(len(res_temp)):
tmp.next = ListNode(res_temp[i])
tmp = tmp.next
return res.next
执行用时：40 ms, 在所有 Python 提交中击败了8.59%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了10.00%的用户
咳咳～时间好感人呀，没办法，好像脑回路跟算法又跑偏了，如果回顾以前做的链表题目，应该要想到递归之类的解题思路，不过不好意思，我是猪 Q_Q，猪就是看见什么是什么.....傻眼中。
方法二：
递归思路，递归的三要素，明确函数功能，找到终止条件，找到等价关系。这句话好像很熟悉，上次的链表题明明有Q...
再默念下，我是猪。
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1: return l2 # 终止条件，直到两个链表都空
if not l2: return l1
if l1.val <= l2.val: # 函数功能
l1.next = self.mergeTwoLists(l1.next,l2) #等价关系
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
执行用时：24 ms, 在所有 Python 提交中击败了83.77%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了10.00%的用户