Topic describes

Merge K sorted linked lists

Merge k sorted lists and return the merged sorted lists. Analyze and describe the complexity of the algorithm.

Example: input: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

title

Method one: violence method

Their thinking

Merge K sorted linked lists. First of all, we directly solve the problem by brute force. Put the val values of all nodes in the linked List into a List, and then sort the List.

Code sample

Java:

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

        // 1. Put the linked List nodes into a List
        List<Integer> arr = new ArrayList<Integer>();
        for (int i = 0; i < lists.length; i++) {
            ListNode cur = lists[i];
            while(cur ! =null) { arr.add(cur.val); cur = cur.next; }}/ / 2. Sort
        Collections.sort(arr);
        
        // 3. Rebuild the linked list
        ListNode res = new ListNode(0);
        ListNode cur = res;
        for(int i = 0; i < arr.size(); i++) {
            ListNode node = new ListNode(arr.get(i));
            cur.next = node;
            cur = cur.next;
        }
        returnres.next; }}Copy the code

Complexity analysis

Time complexity: O(N * log(N)), where N represents the number of all linked list nodes.

  • It takes O(N) time to go through all the values
  • A stable sorting algorithm takes N log N time
  • It takes N log N time to rebuild the list

Space complexity: O(N)

Method two: heap sort method

Their thinking

Use heap to sort the linked list nodes, create a small root heap of size K, first insert K linked list head Pointers into the heap, then take out the top element, at the same time insert the next node of the top element into the minimum heap, and then cycle the operation until all the linked list nodes have been traversed.

Code sample

Java:

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

        // 1. Initialize the small root heap
        PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
    			public int compare(ListNode o1, ListNode o2) {
    				return(o1.val - o2.val); }});for(int i = 0; i < lists.length; i++) {
            if(lists[i] ! =null) queue.add(lists[i]);
        }

        // 2. Fetch the top element and insert the next node of the top element into the small root heap
        ListNode res = new ListNode(0);
        ListNode cur = res;
        while(! queue.isEmpty()) { ListNode top = queue.poll();if(top.next ! =null) {
                queue.add(top.next);
            }
            cur.next = top;
            cur = cur.next;
        }
        returnres.next; }}Copy the code

Complexity analysis

Time complexity: O(N * log(K)), where N represents the number of all linked list nodes and K represents the number of linked lists.

Space complexity: O(K)

Method three: divide and conquer

Their thinking

We divide K lists in half, merge the former K/2 lists, then merge the latter K/2 lists, and then merge the former K/2 lists with the latter K/2 lists to get the final result.

When dealing with the pre-K /2 and post-K /2 linked lists, the idea is the same as the above method. The linked list is continuously divided in a recursive way until the list can no longer be divided, and the linked list is returned to the upper level of the recursion for pin-two merger.

Divide and conquer idea: partition problem –> result of merge subproblem

Code sample

Java:

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

    public ListNode divide(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        ListNode left = divide(lists, lo, mid);
        ListNode right = divide(lists, mid + 1, hi);
        return merge(left, right);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
		if(l1 == null || l2 == null) {
			return (l1 == null)? l2 : l1; }if(l1.val <= l2.val) {
			l1.next = merge(l1.next,l2);
			return l1;
		} else {
			l2.next = merge(l1, l2.next);
			returnl2; }}}Copy the code

Complexity analysis

Time complexity: O(N * log(K)), where N represents the number of all linked list nodes and K represents the number of linked lists.

Space complexity: O(K)