在java中插入一個數字並保留它的排序

Question

我覺得我非常相信我在這段代碼中是正確的。從邏輯上講，這對我來說很合理，但由於某種原因，程序拒絕跑過某個點。我應該這樣做，而不使用專有類或哈希表。我的列表節點是一個基本的單向鏈表。假設我最初有一個虛擬列表，0，我可以將一個數字添加到列表中，但僅此而已。這是除了添加第一個數字之外無法使用的方法。

假設我的名單是0 - > 2。和我試圖加1

public void insert(int newElement) { 
    List marker = head; 
    List temp = new List(newElement, null); 

    if (head.next == null) { 
     head.next = temp; 
    } else { 
     while (marker.next != null) { 
      if (newElement < marker.next.value) { 
       temp.next = marker.next; 
       marker.next = temp; 
       marker = marker.next; 
      } 
     } 
    } 
} 

Answer 1

List marker = head; 
    List temp = new List(newElement, null); 

    if (head.value > temp.value) { 
     head.next = new List(head.value, null); 
     head.value = newElement; 
    }else if(head.next == null) 
    { 
     head.next = temp; 
    } 
    else { 
     while (marker.next != null) { 
      if (newElement < marker.next.value) { 
       temp.next = marker.next; 
       marker.next = temp; 
       break; //we added the node, no need to continue looping 
      } 
      else //we need to iterate to the next node in the list until empty 
      { 
       marker = marker.next; 
      } 
     } 
    } 

Answer 2

public void insert(int val) { 
    Item item = new Item(val); 

    // the case when there is no item (not counting the dummy head) 
    if (head.getNext() == null) { 
     head.setNext(item); 
     item.setNext(null); 
    } else { 
     // if there is at least one item.... 
     Item cursor = head.getNext(); 
     Item prev = cursor; 

     // simply keep looping the list until the new value is less than a value in list 
     // if the new value is greater than all the values in the list... 
     // then the do-while loop will break when null is reached... 
     // at the end of the list 
     do { 
      if (val < cursor.getVal()) { 
       // break and insert 
       break; 
      } 
      prev = cursor; 
      cursor = cursor.getNext(); 
     } while (cursor != null); 

     // insert the item 
     item.setNext(cursor); 

     // the case when the new value is the smallest and is to be inserted at head 
     if (val < head.getNext().getVal()) { 
      head = item; 
     } else prev.setNext(item); 
    } 
} 

這是你的代碼片段：

if (newElement < marker.next.value) { 
    temp.next = marker.next; 
    marker.next = temp; 
    marker = marker.next; 
} 

乘坐鉛筆和紙，並追查這段代碼。你會看到它有什麼問題。請回答look at this並查看附加的圖像。這就是你應該如何真正調試關於鏈表的問題。該圖像不是特定於您的代碼，但它應該讓您知道如何解決這類問題。

Answer 3

這似乎是工作，我目前正在測試它的結果很好。任何人都可以找到我錯過的這段代碼的問題嗎？

public void insert(int newElement) { 
    List marker = head; 
    List temp = new List(newElement, null); 

    if (head.next == null) { 
     head.next = temp; 
    } else { 
     for (marker = head; marker.next != null; marker = marker.next) { 
      if (temp.value < marker.next.value) { 
       temp.next = marker.next; 
       marker.next = temp; 
       break; 
      } 

     } 
     if (marker.next == null && temp.value > marker.value) { 
       marker.next = temp; 

      } 
    } 

}