Вставка в отсортированном двусвязном списке

Question

Мне присваивается указатель на головной узел отсортированного дважды связанного списка и целое число для вставки в список. Мне предлагается создать узел и вставить его в соответствующую позицию в списке так что его упорядоченный порядок поддерживается. Головной узел может быть NULL.

Пример ввода

NULL, то данные = 2

< NULL - 2 < -> 4 < -> 6 -> NULL, то данные = 5

Пример вывода

< NULL - 2 -> NULL

< NULL - 2 < -> 4 < -> 5 < -> 6 -> NULL

Я пробовал вышеуказанную проблему. Но моя программа заканчивается из-за таймаута. Что я делаю неправильно в приведенном ниже коде. Предположим, что класс узла и основная функция уже существуют. Спасибо заранее!!

Node SortedInsert(Node head,int data) { 

    Node newn = new Node(); 

    newn.data = data; 
    newn.prev=null; 
    newn.next = null; 

    Node ptr = head; 
    Node nex=head.next; 

    while(ptr!=null && nex!=null) { 
     if(ptr.data<=newn.data && nex.data>=newn.data) { 
      newn.next = nex; 
      newn.prev = ptr; 
      nex.prev = newn; 
      ptr.next = newn; 
     }    
     else { 
      nex=nex.next; 
      ptr=ptr.next; 
     } 
    } 

    if(ptr!=null && nex==null) { 
     if(ptr.data>=newn.data) { 
      newn.next=ptr; 
      ptr.prev=newn; 
      newn.prev=null; 
      head=newn; 
     } 
     else { 
      ptr.next=newn; 
      newn.prev = head; 
     } 
    } 

    if(head==null) { 
     head = newn; 
    } 

    return head; 

} 

Answer 1

довольно просто: Вы не вырываясь из петли после вставки успешно. Поэтому он продолжает цикл по позиции, которую он вставляет узел сделать крошечные изменения:.

if(ptr.data>=newn.data) 
{ 
    newn.next=ptr; 
    ptr.prev=newn; 
    newn.prev=null; 
    head=newn; 
    break; 
} 

Тем не менее, есть некоторая избыточная кода, написанная. Это короче и не содержит лишний код:

Node SortedInsert(Node head,int data) { 

    Node newn = new Node(); 
    newn.data = data; 

    Node ptr = head; 

    if (ptr == null) { 
     head = newn; 

    } else if (ptr.data > newn.data) { 
     newn.next = ptr; 
     ptr.prev = newn; 
     head = newn; 

    } else { 
     Node nex = head.next; 

     while (nex != null && nex.data <= newn.data) { 
      ptr = nex; 
      nex = nex.next; 
     } 

     ptr.next = newn; 
     newn.prev = ptr; 

     if (nex != null) { 
      nex.prev = newn; 
      newn.next = nex; 
     } 
    } 

    return head; 
} 

Answer 2

Если головной узел является нулевым вы Гет NullPointerException при попытке получить Next/Prev узлы. Вы должны сначала убедиться в этом:

Node sortedInsert(Node head, int data) { 
    Node newn = new Node(); 
    newn.data = data; 
    //Basic case: the list is empty, so the head is null 
    if (head==null) { 
     return newn; 
    } 
    //If node is not null 
    Node aux= head; 
    Node auxPrev; 
    while (aux!=null && aux.data<data) { 
     auxPrev=aux; 
     aux=aux.next; 
    } 
    //auxPrev will be null if we are going to insert in the first position 
    if (auxPrev!=null) 
     auxPrev.next=newn; 
     newn.prev=auxPrev; 
     head=newn; 
    } 
    //aux will be null if we insert in the last position 
    if (aux!=null) { 
     aux.prev=newn; 
     newn.next=aux; 
    } 
    return head; 
}