leetcode23

朱雀 2022-08-09 02:22 130阅读 0赞

LeetCode23----------Merge K Sorted Lists

这道理暴力搜索两两合并排序肯定超时的，这个我试过。。。

题目给的Tag是分治法，我就用分治法来解决的，对整个lists递归两两合并，最后return

在网上看到有用堆的方法解决，这个没有仔细研究，等哪天研究了再更新。

在这里复用了之前两两合并的代码：

class Solution {
    private:
    	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    		if (l2 == NULL)
    			return l1;
    		if (l1 == NULL)
    			return l2;
    		ListNode *head = new ListNode(0);
    		ListNode *r = head;
    		while (l1 && l2)
    		{
    			if (l1->val == l2->val)
    			{
    				ListNode*p1 = new ListNode(l1->val);
    				ListNode*p2 = new ListNode(l2->val);
    				r->next = p1;
    				r = p1;
    				r->next = p2;
    				r = p2;
    				l1 = l1->next;
    				l2 = l2->next;
    			}
    			else if (l1->val < l2->val)
    			{
    				ListNode*p1 = new ListNode(l1->val);
    				r->next = p1;
    				r = p1;
    				l1 = l1->next;
    			}
    			else
    			{
    				ListNode*p2 = new ListNode(l2->val);
    				r->next = p2;
    				r = p2;
    				l2 = l2->next;
    			}
    		}
    		if (!l1)
    		{
    			r->next = l2;
    		}
    		else
    		{
    			r->next = l1;
    		}
    		ListNode * p = head;
    		head = head->next;
    		delete p;
    		return head;
    	}
    public:
    	ListNode* mergeKLists(vector<ListNode*>& lists) {
    		int len = lists.size();
    		if (len == 0)
    			return NULL;
    		if (len == 1)
    			return lists[0];
    		int i = 0;
    		int j = len - 1;
    		while (i < j&&i<len/2)
    		{
    			lists[i] = mergeTwoLists(lists[i], lists[j]);
    			i++;
    			j--;
    			lists.pop_back();//将尾部链表抛弃
    		}
    		return mergeKLists(lists);
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Hard - 23. Merge k Sorted Lists

Topic Linked List Divide and Conquer Heap Description [https://leetcode.

╰半橙微兮°/ 2023年01月06日 05:41/ 0 赞/ 125 阅读

相关 LeetCode题解（2020-10-23）

从今天开始，有空就开始做题，主要不想让脑子太迟钝，先从简单的题目开始。题1：重塑矩阵题目描述在MATLAB中，有一个非常有用的函数 reshape，它可以将

Dear 丶/ 2022年12月17日 08:54/ 0 赞/ 65 阅读

相关 LeetCode数据结构基础---2021/8/23

目录 K个一组翻转链表重排链表最小栈移除无效的括号找出游戏的获胜者 K个一组翻转链表 [K个一组翻转链表][K] 重排链

喜欢ヅ旅行/ 2022年09月07日 12:10/ 0 赞/ 148 阅读

相关剑指Offer 43 / leetcode.23【Js】

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV

谁借莪１个温暖的怀抱￠/ 2022年08月31日 15:13/ 0 赞/ 128 阅读

相关 leetcode23

LeetCode23----------Merge K Sorted Lists 这道理暴力搜索两两合并排序肯定超时的，这个我试过。。。题目给的Tag是分治法，我就用分治

朱雀/ 2022年08月09日 02:22/ 0 赞/ 131 阅读

相关 leetcode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its c

男娘i/ 2022年07月29日 09:19/ 0 赞/ 156 阅读

相关 [leetcode-排序]--23. Merge k Sorted Lists

Question 23. Merge k Sorted Lists > Merge k sorted linked lists and return it as one so

r囧r小猫/ 2022年07月11日 23:57/ 0 赞/ 145 阅读

相关 leetcode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its c

我会带着你远行/ 2022年06月09日 08:08/ 0 赞/ 162 阅读

相关 LeetCode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its c

男娘i/ 2022年05月11日 14:34/ 0 赞/ 142 阅读

相关 LeetCode-23.合并K个排序链表

题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: > 输入: \[ 1->4->5, 1->3->4, 2->6 \] >

╰+攻爆jí腚メ/ 2022年01月26日 13:05/ 0 赞/ 251 阅读