牛客网：将两个单调递增的链表合并为一个单调递增的链表-Python实现-两种方法讲解
方法一和方法二的执行效率，可以大致的计算时间复杂度加以对比，方法一优于方法二
1. 方法一：
思路：
1. 新创建一个链表节点头，假设这里就叫 head3；
2. 因为另外两个链表都为单调递增，所以每次对比这两个链表的第一个节点的值，取出值较小的节点，把其放在 head3 链表的末尾，并在原链表中删除被取出的节点；
3. 直到把原两链表的其中一个链表的所有节点都取走；
4. 把还存有节点的链表整个的追加到 head3 链表的结尾，到此便形成一个节点值从小到大排列的 head3 链表；
代码实现：
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 head = ListNode(22) 11 p = head # p用来当做循环操作的指针 12 # 当两个链表全都不为空，执行循环 13 while pHead1 and pHead2: 14 if pHead1.val <= pHead2.val: 15 p.next = pHead1 16 # 从pHead1中取出头结点时，头结点变为原头结点的next节点 17 pHead1 = pHead1.next 18 elif pHead1.val > pHead2.val: 19 p.next = pHead2 20 pHead2 = pHead2.next # 同理 21 p = p.next # 每次向head3追加一个节点时，指针p偏倚 22 # 如果pHead1不为None，直接把剩下的pHead1追加到pHead3后 23 while pHead1: 24 p.next = pHead1 25 pHead1 = pHead1.next 26 p = p.next 27 # 同理 28 while pHead2: 29 p.next = pHead2 30 pHead2 = pHead2.next 31 p = p.next 32 # 返回的结果，去掉head3创建时的无意义首节点 33 return head.next 34
2. 方法二
思路：
1. 初始化一个空列表；
2. 对比两个递增链表的首节点，将节点值小的节点取出追加到列表的末尾，同时从原链表中删除被取出的节点；
3. 直到把两个链表中的节点都取没，列表中就包含了原来两个链表中所有的节点，并且是一个递增的列表；
4. 最后，使列表中的第 n 个元素的 next 指向列表的第 n+1 个元素，n 的取值为 0~(n-2)，n-1为列表的最后一个元素，使其 next 指向 None；
5. 到此，便形成了一个合并后的递增链表
代码实现：
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 ls = [] 11 # 取出两个链表中头节值较小的节点，追加到ls末尾 12 while pHead1 or pHead2: 13 # 当pHead1链表所有节点被取光的情况 14 if pHead1 == None: 15 ls.append(pHead2) 16 pHead2 = pHead2.next 17 # 同理 18 elif pHead2 == None: 19 ls.append(pHead1) 20 pHead1 = pHead1.next 21 elif pHead1.val <= pHead2.val: 22 ls.append(pHead1) 23 pHead1 = pHead1.next 24 elif pHead1.val > pHead2.val: 25 ls.append(pHead2) 26 pHead2 = pHead2.next 27 # 如果ls为空，说明原两链表都为空，return None 28 if ls == []: 29 return None 30 # 除了列表的最后一个元素，使每个元素的next指向其下一个 31 for i in range(len(ls)-1): 32 ls[i].next = ls[i+1] 33 # 列表最后一个元素的next指向None 34 ls[len(ls)-1].next = None 35 # 返回结果 36 return ls[0] 37