合并两个有序链表

1. 链接：
   https://leetcode.cn/problems/merge-two-sorted-lists/
2. 题目：
   将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
   示例:
   

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

3. 思路：
   1. 第一种，首先对有空链表的情况进行讨论。然后建立一个结果链表head，对l1和l2进行遍历和一一比较，数值小的进入结果链表，并且向后移动一位。当其中一个链表出现为空时，就可以进行return了。
   2. 第二种，迭代，和第一种的思想是一样的，代码更加简洁。
   3. 第三种，递归。
4. 代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //第一种
        //公有部分，针对特殊情况空链表进行判断
        if(list1==NULL)
        return list2;
        else if(list2==NULL)
        return  list1;
        //head指向结果链表的表头，作为返回值
        //tmp结果链表，在后续代码执行中进行变换
        //k存l1或者l2的后续结点，在结果链表插入后，l1或l2可以指向下一个元素
        ListNode *head,*tmp,*k;
        tmp=list1->val<=list2->val?list1:list2;
        head=tmp;
        while(list1!=NULL||list2!=NULL){
        //一个list为空后的返回
            if(list1==NULL){
                tmp->next=list2;
                return head;
            }
            if(list2==NULL){
                tmp->next=list1;
                return head;
            }
            //对结果链表进行尾插
            if(list1->val<=list2->val){
                k=list1->next;
                list1->next=tmp->next;
                tmp->next=list1;
                tmp=list1;
                list1=k;
            }else {
                k=list2->next;
                list2->next=tmp->next;
                tmp->next=list2;
                tmp=list2;
                list2=k;
            }
        }
        return head;


        //第二种，迭代
        //和第一种思路是一样的
        if(list1==NULL)
        return list2;
        else if(list2==NULL)
        return  list1;
        ListNode *pre= new ListNode(-1);
        ListNode *preh=pre;
        while(list1!=NULL&&list2!=NULL){
            if(list1->valval){
                preh->next=list1;
                list1=list1->next;
            }else{
                preh->next=list2;
                list2=list2->next;
            }
            preh=preh->next;
        }
        preh->next=list1==NULL?list2:list1;
        return pre->next;

        //递归
        if(list1==NULL)
        return list2;
        else if(list2==NULL)
        return  list1;
        else  if(list1->valval){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};