首页 > 代码库 > [LeetCode]Merge Two Sorted Lists

[LeetCode]Merge Two Sorted Lists

2024-09-18 09:02:55   217人阅读

题目：Merge Two Sorted Lists

合并两个单链表。

思路：

同时遍历两个单链表，比较每个值，较小的取下来放到新的链表的尾部。

注意：判断空链的情况

ListNode* LeetCode::mergeTwoLists(ListNode* l1, ListNode* l2){
    if (!l1)return l2;
    if (!l2)return l1;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    if (l1->val < l2->val){//l1为头结点
        head = l1;
        l1 = l1->next;
    }
    else{//l2为头结点
        head = l2;
        l2 = l2->next;
    }
    tail = head;
    while (l1 && l2){
        if (l1->val < l2->val){//l1较小
            tail->next = l1;
            l1 = l1->next;
        }
        else{//l2较小
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    if (l1)tail->next = l1;//l1链表不空
    if (l2)tail->next = l2;//l2链表不空
    return head;
}

题目：Merge k Sorted Lists

合并k个单链表。

思路：

设置k个链表指针分别通过这些指针来遍历着k个链表；但是不能像上面那样有一个链表为空就跳出，而要当仅有一个链表不空的时候跳出。

所以每当有一个链表遍历到链尾时，就将它的指针删除。

ListNode* LeetCode::mergeKLists(vector<ListNode*>& lists){
    vector<ListNode*>p;
    for (size_t i = 0; i < lists.size(); i++){
        if (lists.at(i)){//可能数组中有空链
            p.push_back(lists.at(i));
        }
    }
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    while (p.size() > 1){
        int min = 0;
        for (size_t i = 1; i < p.size(); i++){//找到最小的节点
            if (p.at(min)->val > p.at(i)->val)min = i;
        }
        if (head){
            tail->next = p.at(min);//将最小的节点加入尾部
            tail = tail->next;
            p.at(min) = p.at(min)->next;//最小的链表指向下一个
        }
        else{//第一个节点
            head = p.at(min);
            tail = head;
            p.at(min) = p.at(min)->next;
        }
        for (size_t i = 0; i < p.size(); ){//删除已经指向链尾的指针
            if (!p.at(i)){
                p.at(i) = p.at(p.size() - 1);
                p.pop_back();
            }
            else{
                ++i;
            }
        }
    }
    if (p.size()){
        if (head)tail->next = p.at(0);
        else head = p.at(0);//lists中只有一条链表
    }
    return head;
}

 

[LeetCode]Merge Two Sorted Lists


联系
我们