23. 合并K个升序链表

发表评论
642 views

 ›
23. 合并K个升序链表

官方链接

https://leetcode-cn.com/problems/merge-k-sorted-lists/

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

示例:

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

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) return a != null ? a : b;

        ListNode head = new ListNode(-1);
        ListNode dummy = head;
        while(a != null && b != null) {
            if(a.val <= b.val) {
                dummy.next = a;
                a = a.next;
            } else {
                dummy.next = b;
                b = b.next; 
            }
            dummy = dummy.next;
        }
        if (a != null) dummy.next = a;
        if (b != null) dummy.next = b;
        return head.next;

    }
    public ListNode mergeKLists(ListNode[] lists) {

        ListNode result = null;
        for(int i = 0; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }
}