Не удалось перебрать список ссылок в java при использовании этого метода (сложно описать проблему в заголовке)

Question

проблема:

Я работаю над алгоритмом в Leetcode, который объединяет k отсортированных списков. Я написал коды ниже и верил, что все получится. Я могу успешно перебрать все узлы из lists[] (если я прокомментирую эту строку res = insertIntoList(curr,res);), и я могу успешно вставить узлы в список res (если я раскомментирую последние три строки в методе mergeKLists) . Однако, если я просто запустил этот метод без изменений, я получу ошибку Time limit exceeded, где я обнаружил, что curr в while l oop на самом деле не меняется на следующий узел, это продолжайте использовать первый узел и работать снова и снова. Я все перепробовал и не нашел, в чем проблема. Может быть, у вас получится, спасибо, что прочитали все это.

Описание:

23. Merge k Sorted Lists
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
]

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

код:

public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null)
            return null;
        ListNode res = lists[0];
        for(int i = 1; i < lists.length; i++) {
            ListNode curr = lists[i];
            while(curr != null) {
                System.out.println("outside curr1:\t"+curr.val);
                res = insertIntoList(curr,res);
                System.out.println("outside curr2:\t"+curr.val);
                curr = curr.next;
            }
        }
        return res;
        /**
        ListNode res = lists[0];
        ListNode test = lists[1].next.next;
        return insertIntoList(test,res);**/
    }
    
    public ListNode insertIntoList(ListNode toBeInsert, ListNode res) {
        if(toBeInsert.val <= res.val) {
            toBeInsert.next = res;
            return toBeInsert;
        }
        
        ListNode curr = res;
        while(curr != null) {
            System.out.println("inside curr:\t"+curr.val);
            
            if ((toBeInsert.val > curr.val) && (toBeInsert.val > curr.next.val))
                curr = curr.next;
            
            ListNode tmp = curr.next;
            curr.next = toBeInsert;
            toBeInsert.next = tmp;
            break;
        }
        return res;
    }

Answer 1

Ваш алгоритм кажется эффективным. Возможно, ваша ошибка будет здесь, в этой строке:

toBeInsert.next = tmp;

измените его на

toBeInsert = tmp;

Я не уверен, хотя.

Если хотите, вы может использовать Priority Queue для решения этой проблемы, это значительно упрощает:

public class Solution {
    public static final ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, (a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

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

        while (!queue.isEmpty()) {
            curr.next = queue.poll();
            curr = curr.next;

            if (curr.next != null) {
                queue.add(curr.next);
            }
        }

        return dummy.next;
    }
}

Ссылки

• Дополнительные сведения можно найти на Доске обсуждения . Есть множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптот c время / пространство анализ сложности ^{1 , 2} там.