合并两个有序链表(c/c++)(数据结构基础回顾)

超、凢脫俗 2023-02-20 13:37 45阅读 0赞

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYmlndW91c19f_size_16_color_FFFFFF_t_70][]

/**
     * 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;
            }
            if(l2==nullptr)
            {
                return l1;
            }
            ListNode head;
            head.next=nullptr;
            ListNode *k=&head;
            ListNode *cur1=l1;
            ListNode *cur2=l2;
            while(cur1&&cur2)
            {
                if(cur1->val<=cur2->val)
                {
                    k->next=cur1;
                    cur1=cur1->next;
                }
                else
                {
                    k->next=cur2;
                    cur2=cur2->next;
                }
                k=k->next;
            }
            if(cur1==nullptr)
            {
                k->next=cur2;
            }
            else
            {
                k->next=cur1;
            }
            return head.next;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYmlndW91c19f_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627142229228.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYmlndW91c19f,size_16,color_FFFFFF,t_70