как уменьшить сложность двусвязного списка в коде

Question

// Complete the sortedInsert function below.

/*
 * For your reference:
 *
 * DoublyLinkedListNode {
 *     int data;
 *     DoublyLinkedListNode next;
 *     DoublyLinkedListNode prev;
 * }
 *
 */
static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {
    DoublyLinkedListNode Leader=head;
    DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);
    while(Leader.next!=null){

        if(data>Leader.data){
            Leader = Leader.next;
        } 
        else {
            if(Leader.prev == null) {
                newNode.next = Leader;
                Leader.prev = newNode;
                head = newNode;
                return head;
            } 
        }

    }
    if(Leader.next == null) {
        if(data<Leader.data) {
            newNode.prev = Leader.prev;
            newNode.next = Leader;
            Leader.prev.next = newNode;
            return head;
        } else {
            newNode.prev = Leader;
            Leader.next = newNode;
            return head;
        }


    }
       return head;



}

в вышеописанном методе вставки, как уменьшить сложность этого двусвязного списка, это хакеркэнкский вопрос. Я получаю тайм-ауты для тестовых случаев.

Answer 1

Ваш код никогда не выйдет из цикла while.

Давайте возьмем пример. Список = [(1), (4), (4)] (только 1 элемент). Новый узел (4). Ваш результат должен быть [(1), (4), (4), (4)]. Но давайте пройдемся по вашему коду и проверим, что произойдет. Первоначально Лидер = (1)

while(Leader.next!=null){ // 1

    if(data>Leader.data){  // 3
        Leader = Leader.next;
    } 
    else { // 6
        if(Leader.prev == null) { // 7
            newNode.next = Leader;
            Leader.prev = newNode;
            head = newNode;
            return head;
        } 
    }

}

В строке 1 проверка пройдет (так как (1) .следующее не равно нулю; на самом деле это (4)).

В строке 3 ((4)> (1)). Проверьте пропуск. Лидер = (1) .следующий = (4). Перейти к строке 1

В строке 1 проверка пройдет (так как (4) .next не нуль; на самом деле это (4)).

В строке 3 ((4)> (4)). Проверьте Fail. Введите строку 7

В строке 7 проверка не будет выполнена ((4) .prev не равно нулю; фактически это (4) - 1-й 4). Никаких обновлений в Лидере не будет. Лидер останется прежним, и вы войдете в бесконечный цикл отсюда.

Вы должны позаботиться об этом. Возможно, страница обсуждения проблемы поможет. Но попробуйте.

Моя собственная попытка включена ниже: