题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
基本思想
设定一个哨兵节点pHead，维护prev的next指针。next指针应该指向哪儿呢？需要比较pHead1和pHead2的“下一个”节点，prev指向两者中小的的那个。
所以每次比较，先判断谁小，将prev的next指向它。再往后挪一个。
每次循环，不管1或者2哪一个小，prev都要往后再走一个。（此处下一个目标节点已经确定好了，即1和2中更小的那个）
最后考虑，1或2其中必定有一个剩余一些节点，这些节点中最小的那个，也是大于等于合并链表最大节点的，所以将它直接加入合并链表（已经排好序了）。
Python
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
pHead = ListNode(-1)
prev = pHead
while pHead1 and pHead2:
if pHead1.val < pHead2.val:
prev.next = pHead1
pHead1 = pHead1.next
else:
prev.next = pHead2
pHead2 = pHead2.next
prev = prev.next
prev.next = pHead1 if pHead1 is not None else pHead2
return pHead.next
网友评论