以下解法一定要升序有序链表
struct LinkNode{
int value;
LinkNode* next;
LinkNode(int x): value(x), next(NULL){}; //节点的构造函数
};
//遍历合并
LinkNode* mergeByIterator(LinkNode * l1, LinkNode* l2){
LinkNode* head = LinkNode(0);
LinkNode* tail = head; //初始化一个头部哨兵节点，
//哨兵负责记录新链的首个节点，同时弄一个尾巴，
//用尾插法将有序链表结点插入
while(l1 && l2){ //两链不为空的情况下移动指针
if(l1 -> value < l2 -> value){
tail -> next = l1; //当l1的值少于l2的时候，将该结点插尾
l1 = l1 -> next; //l1让位，移动下一个结点，让尾移动到它的位置
}
else {
tail -> next = l2; //当l2少于l1 的时候，将该结点插尾
l2 = l2 -> next; //l2让位，移动到下一个结点，让尾移动它的位置
}
tail = tail -> next;
}
if(l1) tail -> next = l1; //当循环结束后，哪个链不为空，后面肯定是顺序的，后面的结点直接插尾
if(l2) tail -> next = l2;
return head -> next;
}
//递归合并
LinkNode* mergeWithRecursion(LinkNode* l1, LinkNode* l2){
//递归返回条件,当我为NULL的时候，把我的下一个点连到比我大大不为空的有序表
if(l1 == NULL){
return l2;
}
if(l2 == NULL) {
return l1;
}
if(l1 < l2) {
l1 -> next = mergeWithRecursion(l1 -> next, l2);
//邻居，你和l2比较
//将比我(l1)大的点插入到我后面
return l1; //完成连接后返回我自己
}
else {
l2 -> next = mergeWithRecursion(l1, l2 -> next);
//邻居，你和l1比较
//大的跟到我后面
return l2;
}
}
