双重链表添加值

Question

我试图合并两个(预排序)双链表在一起，它不断得到无限循环或一个元素列表时，试图添加。

下面代码的预期结果应该是:

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

So I Have:

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

注意，这是在一个不同的类中，你不能直接访问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
            }
}

这肯定需要一些调整，这取决于你的实现，但逻辑是合理的，我相信。