博客

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

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

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = [0]

输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按 非递减顺序 排列

这道题我看了

力扣的官方解题思路

后选择了迭代法，那个动图真的很形象，可以结合代码理解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* pHead=(struct ListNode*)malloc(sizeof(struct ListNode));//动态分配一个节点以便找到合并后的链表；
    struct ListNode* pre=pHead;//pre在两个链表中移动传递数值；
    while(l1!=NULL&&l2!=NULL)
    {
        if(l1->val<l2->val)
        {
            pre->next=l1;
            l1=l1->next;
        }
        else
        {
            pre->next=l2;
            l2=l2->next;
        }
        pre=pre->next;
    }
    pre->next=(l1==NULL)?l2:l1;//链表长度可能会不相同，将最长的链表最后一部分直接挂到已经排序好的链表后面
    return pHead->next;
}

来个递归解法：

1，如果有一个链表为空，则返回那个非空链表；

2，若非空，如果l1的val小于等于l2的val，则让l1的指针域指向l1->next和l2合并的有序链表（因为此时l1已经是合并后链表的头节点了，只需要从l1的下一个节点开始和l2合并就可以了），并返回l1；否则，就让l2的指针域指向l2->next和l1合并的有序链表，并返回l2；

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(!l1||!l2)
        return l1?l1:l2;
        if(l1->val<=l2->val)
        {
            l1->next=mergeTwoLists(l1->next,l2);
            return l1;
        }
        else
        {
            l2->next=mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};