LeetCode--021--合并两个有序链表

问题描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

方法1：

 1 class Solution(object):
 2     def mergeTwoLists(self, l1, l2):
 3         """
 4         :type l1: ListNode
 5         :type l2: ListNode
 6         :rtype: ListNode
 7         """
 8         p = dummy = ListNode(-1)
 9         while l1 and l2:
10             if l1.val <= l2.val:
11                 p.next = ListNode(l1.val)
12                 l1 = l1.next
13             else:
14                 p.next = ListNode(l2.val)
15                 l2 = l2.next
16             p = p.next
17         p.next = l1 or l2
18         return dummy.next

方法2：递归

 1 class Solution(object):
 2     def mergeTwoLists(self, l1, l2):
 3         """
 4         :type l1: ListNode
 5         :type l2: ListNode
 6         :rtype: ListNode
 7         """
 8         if l1 == None:
 9             return l2
10         if l2 == None:
11             return l1
12         mergel = None #设置新链表
13         if l1.val < l2.val:
14             mergel = l1
15             mergel.next = self.mergeTwoLists(l1.next, l2)
16         else:
17             mergel = l2
18             mergel.next = self.mergeTwoLists(l1, l2.next)
19         return mergel
20