首页 > 代码库 > 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个排序的单链表)