題目描述

輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。

示例1：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
限制：

0 <= 鏈表長度 <= 1000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof

解題思路

對兩個鏈表進行分析，若鏈表1的頭節(jié)點小于鏈表2的頭節(jié)點，則將鏈表1的頭節(jié)點“彈出”，并將其添加到新的合成鏈表后面，鏈表1剩下的部分和鏈表2再進行比較，重復上述過程，直到兩個兩個鏈表為空。比較和“彈出”的過程是重復的，因此可采用遞歸法進行實現(xiàn)。

代碼

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


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;

    struct ListNode *phead = NULL;
    if(l1->val < l2->val)
    {
        phead = l1;
        phead->next = mergeTwoLists(l1->next, l2);
    }
    else
    {
        phead = l2;
        phead->next = mergeTwoLists(l1, l2->next);
    }

    return phead;
}

執(zhí)行結(jié)果