在已排序的雙向鏈表中插入

Question

我給出了指向已排序的雙向鏈表的頭節點和要插入到列表中的整數的指針。我被告知創建一個節點並將其插入到列表中的適當位置以便維護其排序的順序。頭節點可能爲NULL。

採樣輸入

NULL，數據= 2

NULL < - 2 < - > 4 < - > 6 - > NULL，數據= 5

樣本輸出

NULL < - 2 - > NULL

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

我試過了上面的問題。但是我的程序因爲timeout而終止。我在下面的代碼中做了什麼錯誤。假設節點類和主要功能已經存在。提前謝謝了！！

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異常，而試圖獲得下/上一個節點。您應該首先檢查：

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; 
}