当前位置：首页 > news >正文

LeeCode 2125 合并两个（K个）有序链表

news 来源：原创 2024/4/24 15:07:55

关于合并两个有序链表，LeeCode官方提供了两种解决办法;

一、迭代

listnode* mergetwolist(listnode* l1, listnode* l2)  //  迭代
{
    listnode* prehead = new listnode(-1);   //创建哨兵结点
    listnode* pre = prehead;  //创建pre指针，
    while (l1 != nullptr && l2 != nullptr)
    {      // l1、l2都不为空，初始时，l1指向l1的第一个结点 l2指向l2的第一个结点
        if (l1->val < l2->val) // l1小于l2，则让pre指向第一个结点，l1往后移动，继续与l2指向的值作比较
        {
            pre->next = l1;
            l1 = l1->next;
        }
        else
        {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;  //pre后移，始终指向已合并区序列的最后一个结点
    }
// 循环，直到l1 或 l2 为空，l1遍历完成后，就把l2指向的剩余链表接到已合并区的后边，l2同理
    pre->next = l1 == nullptr ? l2 : l1;

    return prehead->next;  // 返回第一个合并后链表的第一个结点
}

二、递归

递归这种方法，理解起来比较吃力，不太懂。


    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;
        }
    }

以下是我的理解

然后是合并K个有序链表，看到这个问题的时候，很快就想到了在合并两个有序链表的基础上改一改，就OK了。具体思路就是，两两合并，直到所有的链表都合并到一块。

ListNode* mergeKList(vector<ListNode*>& lists)
{
    ListNode* ans = nullptr;
    for (int i = 0; i < lists.size(); ++i)
        ans = mergeTwoList(ans, lists[i]);
    return ans;
}

能看懂合并两个，就能看懂合并K个，这个没啥说的。就这样