首页 > 代码库 > Leetcode23--->Merge K sorted Lists(合并k个排序的单链表)
Leetcode23--->Merge K sorted Lists(合并k个排序的单链表)
题目： 合并k个排序将k个已排序的链表合并为一个排好序的链表，并分析其时间复杂度 。
解题思路： 类似于归并排序的思想，lists中存放的是多个单链表，将lists的头和尾两个链表合并，放在头，头向后移动，尾向前移动，继续合并，直到头和尾相等，此时已经归并了一半， 然后以同样的方法又重新开始归并剩下的一半。时间复杂度是O(logn)，合并两个链表的时间复杂度是O（n）,则总的时间复杂度大概是O（nlogn）；合并两个单链表算法可以参考Leetcode21中的解法：http://www.cnblogs.com/leavescy/p/5879625.html
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public ListNode mergeKLists(ListNode[] lists) {11 if(lists == null|| lists.length == 0)12 return null;13 if(lists.length == 1)14 return lists[0];15 int end = lists.length - 1;16 int begin = 0;17 while(end > 0) // 将lists的头和尾进行归并，然后将结果存放在头，头向后移动，尾向前移动，直到begin=end,则已经归并了一半，此时将begin=0,继续归并18 {19 begin = 0;20 while(begin < end)21 {22 lists[begin] = combineTwoList(lists[begin], lists[end]);23 begin ++;24 end --;25 }26 }27 28 return lists[0];29 }30 public ListNode combineTwoList(ListNode head1, ListNode head2) // head1和head2为头节点的两个单链表的合并31 {32 if(head1 == null && head2 == null) // 如果两个单链表都不存在，则返回null33 return null;34 if(head1 == null) // 如果head1不存在，则直接返回head235 return head2;36 if(head2 == null)37 return head1;38 ListNode pHead = null;39 if(head1.val > head2.val) // 根据head1与head2的值，决定头节点40 {41 pHead = head2;42 pHead.next = combineTwoList(head1, head2.next);43 }44 else45 {46 pHead = head1;47 pHead.next = combineTwoList(head1.next, head2);48 }49 return pHead;50 }51 }
Leetcode23--->Merge K sorted Lists(合并k个排序的单链表)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。