题目描述

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

• 思路
  按顺序合并所有的链表并返回头结点。
  法一：优先队列存储所有的链表头结点，每次取最小值连接并使它的下一个加入到队列中。
  法二：从第一个链表开始依次合并后再返回头结点。

//法一
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0)
            return null;

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), 
                                                                    new Comparator<ListNode>(){
            @Override
            public int compare(ListNode l1, ListNode l2){
                if(l1.val > l2.val)
                    return 1;
                else if(l1.val < l2.val)
                    return -1;
                else
                    return 0;
            }
        });

        ListNode head = new ListNode(0);
        ListNode Head = head;

        for(ListNode list : lists){
            if(list != null)
                queue.add(list);
        }

        while( !queue.isEmpty()){
            head.next = queue.poll();
            head = head.next;
            if(head.next != null)
                queue.add(head.next);
        }

        return Head.next;
    }
}

//法二
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0)
            return null;

        ListNode head = lists.get(0);
        
        for(int i=1; i<lists.size(); i++){
            head = margeList(head, lists.get(i));
        }
        
        return head;
    }
    
    public ListNode margeList(ListNode n1, ListNode n2){
        ListNode head = new ListNode(0);
        ListNode Head = head;
        
        while(n1 != null && n2 != null){
            if(n1.val <= n2.val){
                head.next = n1;
                n1 = n1.next;
            }else{
                head.next = n2;
                n2 = n2.next;
            }
            head = head.next;
        }
        
        head.next = (n1 == null ? n2: n1);
        
        return Head.next;
    }
}