合并两个有序链表

• 有关题目
• • 题解

题目链接： 合并两个有序链表

有关题目

将两个升序链表合并为一个新的 升序 链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。

示例 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* list1, struct ListNode* list2){
    struct ListNode *ans = NULL;
    if (list1 == NULL)
        return list2;    
    else if (list2 == NULL)
        return list1;
    else if (list1->val > list2->val)
    {
        ans = list2;
        ans->next = mergeTwoLists(list1, list2->next);
        return ans;
    }
    else
    {
        ans = list1;
        ans->next = mergeTwoLists(list1->next, list2);
        return ans;
    }
}

代码二：
参考官方题解

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


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL)
        return list2;    
    else if (list2 == NULL)
        return list1;
    else if (list1->val > list2->val)
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
    else
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
}

法二：迭代
参考官方题解

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


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *preHead = (struct ListNode*)malloc(sizeof(struct ListNode));

    struct ListNode *pre = preHead;
    while(list1 != NULL && list2 != NULL)
    {
        if (list1->val > list2->val)
        {
            pre->next = list2;
            list2 = list2->next;
        }
        else
        {
            pre->next = list1;
            list1 = list1->next;
        }

        pre = pre->next;
    }

	//合并完之后，最多只剩下一个链表未合并，此时只需将链表末尾指向未合并完的链表即可
    pre->next = list1 == NULL ? list2 : list1;

    return preHead->next;
}