• 刷题仓库地址
• 4. Median of Two Sorted Arrays
• 10. Regular Expression Matching
• 23. Merge k Sorted Lists
• 25. Reverse Nodes in k-Group
• 30. Substring with Concatenation of All Words
• 32. Longest Valid Parentheses
• 37. Sudoku Solver

---

23. Merge k Sorted Lists

Description

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

Example

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Translation

合并k个已排序的链接列表并将其作为一个排序列表返回。分析并描述其复杂性。

Ideas

分治 + 归并排序。将数组进行分支，直到每组有两个链表的时候，把这两个链表进行归并排序。

Note

Accept Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class MergekLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return divide(0, lists.length - 1, lists);
    }

    private ListNode divide(int start, int end, ListNode[] listNodes) {
        if (start == end) {
            return listNodes[start];
        }
        ListNode left = divide(start, (start + end) / 2, listNodes);
        ListNode right = divide((start + end) / 2 + 1, end, listNodes);
        return mergeTwoLists(left, right);
    }

    public ListNode mergeTwoLists(ListNode leftList, ListNode rightList) {
        if (leftList == null) return rightList;
        if (rightList == null) return leftList;

        if (leftList.val < rightList.val) {
            leftList.next = mergeTwoLists(leftList.next, rightList);
            return leftList;
        } else {
            rightList.next = mergeTwoLists(leftList, rightList.next);
            return rightList;
        }
    }
}