合并两个有序链表

以下解法一定要升序有序链表

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;
}
}