java - 交替合并两个链表，同时寻找最大值作为头

Question

我正在开发一个链表程序，它允许我只循环列表一次，并且我无法将列表的元素复制到另一个数据结构。

假设列表不为空(至少有一个节点)并且最后一个节点的下一个节点为空。

下面的方法应该合并两个链表，合并后的链表的头应该是两个链表中的最大值。以下值在两个列表之间交替。

例如，如果我的输入是:

1 2 4 

3 5 6 7 8 9

我的输出是:

3 1 5 2 6 4 7 8 9

我弄清楚了如何分配头部，但我不知道如何正确合并列表的其余部分。

这是我的代码:

    public class LinkedListNode {
    private int value;
    private LinkedListNode next;

    public LinkedListNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public LinkedListNode getNext() {
        return next;
    }

    public void setNext(LinkedListNode next) {
        this.next = next;
    }
}

    public static LinkedListNode mergeLists (LinkedListNode head1, LinkedListNode head2){
        LinkedListNode firstList = head1;
        LinkedListNode secondList = head2;
        LinkedListNode tmp = new LinkedListNode(0);
        LinkedListNode result = head1;
        int checkWhichList=0;
        while(firstList!=null && secondList!=null){
            if (firstList.getValue()<=secondList.getValue()){
                result=secondList;
            }
            if (checkWhichList%2==0){
                tmp.setNext(head2.getNext());
                checkWhichList++;
            }
            else
                tmp.setNext(head1.getNext());
        }

        result.setNext(tmp);
        return result;
    }

Answer 1

一旦确定哪个节点具有最大值，您必须将两个头添加到结果(首先是最大值)，然后移动firstList和secondList的指针

现在，您继续添加两个列表的结果，同时移动到每个列表的下一个节点，直到两个列表都不指向任何内容

示例:(以firstList为头的情况为例)

if(firstList.getValue() > secondList.getValue()) {
    //here firstList will be the head
    result = firstList;
    result.setNext(secondList);
    firstList = firstList.getNext();
    secondList = secondList.getNext();

    //Now alternating (adding firstList node before secondList)
    while(firstList != null || secondList != null) {
        if(firstList != null) {
            result.setNext(firstList);
            firstList = firstList.getNext();
        }        
        if(secondList != null) {
            result.setNext(secondList);
            secondList = secondList.getNext();
        }
    }
} else {
   //here secondList will be the head
   //continue with the code
}