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

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

}

这肯定需要根据您的实现进行一些调整，但我相信逻辑是合理的。