Java - 雙鏈表添加值

Question

我試圖將兩個（預先排序的）雙向鏈表合併在一起，並且在嘗試添加時會一直收到無限循環或一個元素列表。

代碼的預期結果下面應該是名單：

[0,1,2,3,4,5,6,7,8,9] 

，所以我必須：

public static void main(String[] args) { 
    TheLinkedList<Integer> oddList = new TheLinkedList<Integer>(); 
    TheLinkedList<Integer> evenList = new TheLinkedList<Integer>(); 

    // Test lists 
    oddList.add(new Integer(9)); 
    oddList.add(new Integer(7)); 
    oddList.add(new Integer(5)); 
    oddList.add(new Integer(3)); 
    oddList.add(new Integer(2)); 
    oddList.add(new Integer(1)); 

    evenList.add(new Integer(8)); 
    evenList.add(new Integer(6)); 
    evenList.add(new Integer(4)); 
    evenList.add(new Integer(2)); 
    evenList.add(new Integer(0)); 

    //System.out.println(oddList.toString()); 
    //System.out.println(evenList.toString()); 
    oddList.merge(evenList); 
    //System.out.println(theList.toString()); 
} 

注意這是一個不同的類，你不能accesss oddList或evenList直接

// Self explanatory getter and setter methods 
public void add(T newValue) { 
    head = new Node<T>(newValue, head, null); 
    if (head.getNext() != null) 
     head.getNext().setPrevious(head); 
    else 
     tail = head; 
    count++; 
} 

public void merge(TheLinkedList<T> two) { 
    do { 

     if (head.getValue().compareTo(two.head.getValue()) <= 0) { 
      head = head.getNext(); 
      continue; 
     } 
     if (head.getValue().compareTo(two.head.getValue()) >= 0){ 
      two.head = two.head.getNext(); 
     } 
    } while (head != null && two.head != null); 
} 

Answer 1

我在這裏看不到任何實際的合併？假設列表按照降序排列，則應該將一個列表的頭部與另一個列表的頭部進行比較，如果另一個列表的值小於主列表的值，則應該將該值插入到主列表中到您的頭節點的下一個節點並轉到下一個值。您需要小心，因爲如果要正確安裝，添加到主列表中的節點需要引用下一個和上一個項目。

如果不能保證順序，那麼就我所知，您需要先對列表進行排序，然後合併它們以防止在最壞的情況下多次遍歷整個引用鏈表。

編輯：這是一個代碼示例。你也許可以這樣做，也是遞歸，但遞歸讓我的頭傷得這麼...

public void merge(TheLinkedList<T> two) { 
Node workingNodeOnOne = this.head; 
Node workingNodeOnTwo = two.head; 

while (workingNodeOnTwo != null) 
     if (workingNodeOnOne.getValue().compareTo(workingNodeOnTwo.getValue()) < 0) { 
      //this is if the value of your second working node is greater than the value of your first working node. 
      //add the two.head.getValue() value of your current list here before the first working node... 
      this.addBefore(workingNodeOnTwo.getValue(), workingNodeOnOne) 
      //note that this does change the value of this.head, but it doesn't matter as we are sorted desc anyways 

      //given the constraints of what you have presented, you should never even hit this code block 
      workingNodeOnTwo = workingNodeOnTwo.next(); 
     } 
     else { //this is if the head value of second list is less than or equal to current head value, so just insert it after the current value here 

      this.add(workingNodeOnTwo.getValue(), workingNodeOnOne); //insert the value of the second working node after our current working node 
      workingNodeOnOne = workingNodeOnOne.next(); 
      workingNodeOnTwo = workingNodeOnTwo.next(); //go on to the next nodes 
      } 

} 

這是肯定會需要一些調整，這取決於您的實現，但邏輯是合理的，我相信。