合并K个排序链表

雨点打透心脏的1/2处 2022-01-14 23:35 205阅读 0赞

## 题目描述 ##

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6

## 解法 ##

归并排序法

public ListNode mergeKLists(ListNode[] lists) { 
    		if(lists == null || lists.length<1) { 
    			return null;
    		}
    		return solve(lists, 0, lists.length-1);
    		
        }
    	
    	private ListNode solve(ListNode[] lists, int left, int right) { 
    		if(left == right) { 
    			return lists[left];
    		}
    		
    		int mid = (left +right)>>1;
    		ListNode leftNode = solve(lists, left, mid);
    		ListNode rightNode = solve(lists, mid+1, right);
    		return merge(leftNode, rightNode);
    	}
    	
    	private ListNode merge(ListNode left, ListNode right) { 
    		if(left == null) { 
    			return right;
    		}
    		if(right == null) { 
    			return left;
    		}
    		ListNode start = new ListNode(0), head = start;
    		while(left != null && right != null) { 
    			if(left.val<right.val) { 
    				start.next = left;
    				left = left.next;
    			}else { 
    				start.next = right;
    				right = right.next;
    			}
    			start = start.next;
    		}
    		if(left == null && right != null) { 
    			start.next = right;
    		}else if (left!= null && right == null) { 
    			start.next = left;
    		}
    		return head.next;
    	}

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 23. 合并K个排序链表（C++）

p.s python版——>[leetcode 23：合并 k 个排序链表][leetcode 23_ k] 题目合并 k 个排序链表，返回合并后的排序链表。请分析和

た入场券/ 2023年07月13日 03:28/ 0 赞/ 2 阅读

相关 leetcode23 合并K个排序链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

分手后的思念是犯贱/ 2023年06月19日 06:49/ 0 赞/ 20 阅读

相关合并k个升序链表

> 合并K个升序链表 > 给你一个链表数组，每个链表都已经按升序排列。 > 请你将所有链表合并到一个升序链表中，返回合并后的链表。 > 示例 1： > 输入：l

喜欢ヅ旅行/ 2022年12月18日 02:53/ 0 赞/ 181 阅读

相关合并 k 个排序链表

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

傷城~/ 2022年04月22日 11:46/ 0 赞/ 155 阅读

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

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

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

相关合并K个排序链表

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

男娘i/ 2022年01月20日 04:07/ 0 赞/ 191 阅读

相关合并K个排序链表

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

雨点打透心脏的1/2处/ 2022年01月14日 23:35/ 0 赞/ 206 阅读

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

> 知乎ID: 码蹄疾 > 码蹄疾，毕业于哈尔滨工业大学。 > 小米广告第三代广告引擎的设计者、开发者； > 负责小米应用商店、日历、开屏广告业务线研发；

痛定思痛。/ 2021年12月17日 08:53/ 0 赞/ 242 阅读

相关 leetcode【23】合并K个排序链表

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

偏执的太偏执、/ 2021年10月03日 01:42/ 0 赞/ 349 阅读

相关合并K个排序链表

合并K个排序链表题目描述 ![5057999-3fd09622a0f9a1f2.png][] 基本思路这道题属于双链表合并的进阶。理解这道题首先需要了解

清疚/ 2021年10月01日 11:26/ 0 赞/ 278 阅读