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

      } 
    } 

}