python 合并两个排序的链表

题目描述

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

样例

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

思路：

新建一个空链表，然后比较 l1 和 l2 里面的值得大小，将小的值插进去

 1 # -*- coding:utf-8 -*-
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 class Solution:
 7     # 返回合并后列表
 8     def Merge(self, pHead1, pHead2):
 9         # write code here
10         if pHead1 == None:
11             return pHead2
12         if pHead2 == None:
13             return pHead1
14         new = ListNode(0)
15         l1 = pHead1
16         l2 = pHead2
17         l3 = new
18         while l1 is not None and l2 is not None:
19             if l1.val < l2.val:
20                 l3.next = l1
21                 l1 = l1.next
22             else:
23                 l3.next = l2
24                 l2 = l2.next
25             l3 = l3.next
26             
27         else:
28             if l1 == None :
29                 l3.next = l2
30                 
31             else:
32                 l3.next = l1
33         return new.next
34

注意一点就是最后要返回的是 new.next 而不是new