Leetcode系列之链表（13）
题目：
合并k个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。
思路：
典型的多路归并问题
代码：
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
while(lists.size() > 1) {
ArrayList<ListNode> newLists = new ArrayList<ListNode>();
for(int i=0;i+1<lists.size();i=i+2) {
ListNode mergedList = mergeTwoLists(lists.get(i), lists.get(i+1));
newLists.add(mergedList);
}
if(lists.size()%2 == 1) {
newLists.add(lists.get(lists.size()-1));
}
lists = newLists;
}
return lists.get(0);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode point = head;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
point.next = l1;
l1 = l1.next;
}
else {
point.next = l2;
l2 = l2.next;
}
point = point.next;
}
if(l1!=null) {
point.next = l1;
}
if(l2!=null) {
point.next = l2;
}
return head.next;
}
}
