Merge K ascending linked lists

You are given an array of linked lists. Each list has been sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: linked list traversal
  • First, if lists are null or empty, null is returned.
  • Then, iterate over the linked list in the number group, record the minimum value min and the corresponding array index minIndex in each iteration process, put min into the result, and move the linked list with the array index minIndex one bit further. The condition of iteration termination is that the loop ends when all the linked lists in the array are empty. When the traversal is complete, result is returned.
public class LeetCode_023 {
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        int count = 0;
        ListNode result = new ListNode(-1);
        ListNode next = result;
        do {
            count = 0;
            int min = Integer.MAX_VALUE, minIndex = -1;
            for (int i = 0; i < lists.length; i++) {
                if(lists[i] ! =null) {
                    count++;
                    if(min > lists[i].val) { min = lists[i].val; minIndex = i; }}}if (count > 0) {
                next.next = newListNode(min); lists[minIndex] = lists[minIndex].next; next = next.next; }}while (count > 0);
        return result.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);

        ListNode result = mergeKLists(new ListNode[]{l1, l2, l3});
        while(result ! =null) {
            System.out.print(result.val + ""); result = result.next; }}}Copy the code

When everything seems to be going against you, remember that the plane takes off against the wind, not with it.