剑指offer面试题25：合并两个排序的链表

 题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：  输入：1->2->4, 1->3->4        输出：1->1->2->3->4->4

思路一：迭代
1、设置 res 为哑结点，放置于新链表之前，最后返回的就是 res->next ；设置 p 为当前节点，从 res 开始。
2、当两个链表都非空时进入循环，令新链表的下一个节点 p->next 为 val 更小的节点，相应的链表节点后移一位。
3、每次循环记得 p 也要后移一位。
4、如果循环结束后还有链表非空，p 指向非空链表。
5、返回 res->next 。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* res = new ListNode(-1);
        ListNode* p = res;

        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val <= l2->val)
            {
                 p->next = new ListNode(l1->val);
                 l1 = l1->next;
            }
            else
            {
                p->next = new ListNode(l2->val);
                l2 = l2->next;
            } 
            p = p->next;
        }

        while(l1 != NULL && l2 == NULL)
        {
            p->next = new ListNode(l1->val);
            l1 = l1->next;
            p = p->next;
        }
        
        while(l1 == NULL && l2 != NULL)
        {
            p->next = new ListNode(l2->val);
            l2 = l2->next;
            p = p->next;
        }

        return res->next;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* res = new ListNode(-1);
        ListNode* p = res;

        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val <= l2->val)
            {
                 p->next = l1;
                 l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            } 
            p = p->next;
        }

        if(l1 != NULL)  //if(l1 != NULL && l2 == NULL)
        {
            p->next = l1;    
        }

        if(l2 != NULL)  //if(l1 == NULL && l2 != NULL)
        {
            p->next = l2;     
        }

        return res->next;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        // 遍历两个链表，比较大小合并。
        // 申请一个伪头节点
        ListNode* res = new ListNode(-1);
        // p用来指向新插入的节点
        ListNode* p = res;

        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val <= l2->val)
            {
                 p->next = l1;
                 l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            } 
            p = p->next;
        }

        // 若l1 == null，直接把l2后面插入进来。否则l2 == null，直接把l1后面插入进来。
        // 跳出循环的条件是有一个为空了。
        p->next = l1 != NULL ? l1 : l2;

        return res->next;
    }
};

 思路二：递归
1、特判：如果有一个链表为空，返回另一个链表
2、如果 l1 节点值比 l2 小，下一个节点应该是 l1，应该return l1，在return之前，指定 l1 的下一个节点应该是 l1->next 和 l2 俩链表的合并后的头结点
3、如果 l1 节点值比 l2 大，下一个节点应该是 l2，应该return l2，在return之前，指定 l2 的下一个节点应该是 l1 和 l2->next 俩链表的合并后的头结点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1 == NULL && l2 == NULL) return NULL;

        // 新建一个头结点
        ListNode* res = NULL;

        //如果l1.val <= l2.val，那么头结点的值为l1.head的值，然后开始递归
        if(l1->val <= l2->val)
        {
            res = l1;
            res->next = mergeTwoLists(l1->next,l2);
        }
        //否则，头结点的值为l2.head的值，然后开始递归
        else
        {
            res = l2;
            res->next = mergeTwoLists(l1,l2->next);
        }
        return res;
    }   
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1->val <= l2->val) 
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } 
        else 
        {
            l2->next = mergeTwoLists(l1, l2->next);    
            return l2;
        }
    }
};