【LeetCode每日一题】:链表（C和C++版本）

用户11915063

发布于 2025-11-20 09:49:44

130

题目链接：

21.合并两个有序链表

题目描述：

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

示例：

思路：

首先判断链表是否为空，若l1为空，则直接返回l2即可，若l2为空，则直接返回l1即可
当链表不为空时，判断l1与l2节点的值的大小，小的放在前面，然后让链表往后走一个节点
当其中一个链表为空时，尾节点->next指向不为空链表即可

代码实现：

C版本：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1==NULL)
    {
        return list2;
    }    
    if(list2==NULL)
    {
        return list1;
    }
    ListNode*Head,*Tail;
    Head=Tail=NULL;
    Head=Tail=(ListNode*)malloc(sizeof(ListNode));

    ListNode*l1=list1;
    ListNode*l2=list2;


    while(l1!=NULL&&l2!=NULL)
    {
        if(l1->val<l2->val)
        {
            Tail->next=l1;
            Tail=Tail->next;
            l1=l1->next;
        }
        else
        {
            Tail->next=l2;
            Tail=Tail->next;
            l2=l2->next;
        }
    }
    if(l1)
    {
        Tail->next=l1;
    }
    if(l2)
    {
        Tail->next=l2;
    }
    ListNode* newHead=Head->next;
    free(Head);
    Head=NULL;
    return newHead;
}

C++版本：

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