JZTXT

【leetcode】【21】【合并两个有序链表】

发布时间 2023-06-30 08:43:46作者: laolang2016

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* list1, ListNode* list2) {
        // 都是空返回空节点
        if (nullptr == list1 && nullptr == list2) {
            return list1;
        }
        // 一个为空则返回不为空的列表
        if (nullptr != list1 && nullptr == list2) {
            return list1;
        }
        if (nullptr == list1 && nullptr != list2) {
            return list2;
        }

        // l1 头节点不大于 l2 头结点
        ListNode* l1 = list1;
        ListNode* l2 = list2;
        if (list1->val > list2->val) {
            l1 = list2;
            l2 = list1;
        }

        // 开始插入
        ListNode* cursor = l1; // 游标
        while (nullptr != l2) {
            // 去除当前要插入的节点
            ListNode* tmp = l2;
            l2            = l2->next;

            // 找到 l1 中不大于当前插入节点的最后一个节点
            while (nullptr != cursor->next && cursor->next->val <= tmp->val) {
                cursor = cursor->next;
            }
            // 如果已经到 l1 尾部, 直接把 l2 拼接到 l1 后面, 合并结束
            if (nullptr == cursor->next) {
                cursor->next = tmp;
                break;
            }

            // 把当前插入节点追加到 l1 , 并把游标设置为当前插入节点
            tmp->next    = cursor->next;
            cursor->next = tmp;
            cursor       = tmp;
        }

        return l1;
    }
};

测试效果

image