本题来自《剑指offer》 合并两个排序的链表
题目：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：
A:采用递归的方式（C++ Code）
在各链不为空的情况下，比较各头结点的大小，将其作为头结点，之后递归调用。
B:采用循环的方式（Python Code）
需要考虑较为多的因素，代码的鲁棒性是否为空或者只有一个节点。
C++ Code：（递归）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (!pHead1){ //如果1为空，则直接返回2
return pHead2;
}else if(!pHead2){ //如果2为空，则直接返回1
return pHead1;
}
ListNode* MergeNode = NULL;
if (pHead1->val < pHead2->val){ //如果第一个链的头结点小于第二个
MergeNode = pHead1; //则合并的头结点为第一个的头结点
MergeNode->next = Merge(pHead1->next,pHead2); //递归调用下个
}else{
MergeNode = pHead2; //如果第一个链大于或者等于第二的头结点
MergeNode->next = Merge(pHead1,pHead2->next); //则递归调用
}
return MergeNode; //最终返回合并的头结点
}
};
Python Code：（循环方式）
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None: #如果1链的头结点为空，则直接返回2
return pHead2
if pHead2 == None: #如果2链的头结点为空，则直接返回1
return pHead1
'''
首先处理头部分,将两个值的最小作为结果链表的头
'''
if pHead1.val < pHead2.val: #如果1的头结点值小于2头结点的值
head = pHead1 #合并链的头结点是1的头结点
pHead1 = pHead1.next #则将节点后移
else:
head = pHead2 #否则为2为头结点（大于或者等于）
pHead2 = pHead2.next
temp = head #临时变量，为保存下一个节点
'''
其次处理链表只有一个节点的情况，在上面步骤后将那个大的节点挂载到后面的节点中
'''
if pHead1 == None :
temp.next = pHead2
if pHead2 == None:
temp.next = pHead1
while pHead1 and pHead2: #这种情况在各个链表的节点多余两个以上时，并且不为空
if pHead1.val < pHead2.val: #同理将各个链表的头结点分别比较挂载到结果节点的子节点
temp.next = pHead1
pHead1 = pHead1.next
else:
temp.next = pHead2
pHead2 = pHead2.next
temp = temp.next
if pHead1 == None: #如果比较出现结束，将未完的第二个节点挂载到结果节点上
temp.next = pHead2
break
if pHead2 == None:
temp.next = pHead1
break
return head #最终返回子节