我的解法

我用的是迭代的方法，但是写的并不是很好，下面有更好的迭代解法

题目要求将两个升序列表合并成一个程序列表，所以既然已经知道两个列表都是有序的，只需要依次去看两个列表，如果l1[i]比l2[j]要小，则将l1[i]添加到合并链表上，将指针指向l1下一个元素，继续这样比较，直到l1[k] > l2[j]为止，下一步便是将l2的元素添加至合并链表.

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode();
        auto ans = head;
        auto head_l1 = l1, head_l2 = l2;

        // 这里用的 && 符号，当两个列表都为非空时才需要比较
        // 否则只需要把剩下的一个列表所有的元素都附加到合并列表中 
        while (head_l1 != nullptr && head_l2 != nullptr)
        {
            // 附加l1
            while (head_l1 != nullptr && head_l2 != nullptr && head_l1->val <= head_l2->val)
            {
                head->next = head_l1;
                head = head->next;
                head_l1 = head_l1->next;
            }

            // 附加l2
            // 附加l1
            while (head_l2 != nullptr && head_l1 != nullptr && head_l2->val <= head_l1->val)
            {
                head->next = head_l2;
                head = head->next;
                head_l2 = head_l2->next;
            }
        }
        while (head_l1 != nullptr)
        {
            head->next = head_l1;
            head = head->next;
            head_l1 = head_l1->next;
        }
        while (head_l2 != nullptr)
        {
            head->next = head_l2;
            head = head->next;
            head_l2 = head_l2->next;
        }
        return ans->next;
    }
};

迭代解法

下面是官方题解的迭代方法，我觉得更加精简

class Solution1
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode();
        auto ans = head;
        auto l1_head = l1, l2_head = l2;
        while (l1_head != nullptr && l2_head != nullptr)
        {
            if (l1_head->val >= l2_head->val)
            {
                head->next = l2_head;
                head = head->next;
                l2_head = l2_head->next;
            }
            else
            {
                head->next = l1_head;
                head = head->next;
                l1_head = l1_head->next;
            }
        }

        // 判断l1还是l2的结点有剩余
        ListNode *left_nodes = l1_head == nullptr ? l2_head : l1_head;
        head->next = left_nodes;

        return ans->next;
    }
};

递归解法

链表的结构天然具有递归性，下面讲一下这道题怎么用递归，更详细的参考这篇

1. 假设l1,l2共有n个数字，我们在两个列表中选出一个最小的数字结点，并让这个结点指向剩下 n - 1个结点的合并结果
2. 当l1或者l2结点为null时，则返回另一个结点

// 递归解法
class Solution2
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {

        // l1结点为null，不需要继续递归了，只需要把剩下l2里的所有结点附加在链表后面
        if (l1 == nullptr)
        {
            return l2;
        }
         
         // 同上
         if (l2 == nullptr)
        {
            return l1;
        }
        if (l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};