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

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

一旦你确定哪个节点具有最大值，你必须将两个头都添加到result(首先是最大值)，然后移动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
}

Answer 2

你可以试试下面的代码:

public class Test {
public static void main(String args[]) {
    //1 2 4
    //3 5 6 7 8 9
    LinkedListNode list1 = new LinkedListNode(1);
    list1.insert(list1, 2);
    list1.insert(list1, 4);
    LinkedListNode list2 = new LinkedListNode(3);
    list2.insert(list2, 5);
    list2.insert(list2, 6);
    list2.insert(list2, 7);
    list2.insert(list2, 8);
    list2.insert(list2, 9);
    LinkedListNode result = mergeLists(list1, list2);
    while(result!=null){
        System.out.print(result.getValue() + " ");
        result = result.getNext();
    }
}
public static LinkedListNode mergeLists (LinkedListNode head1, LinkedListNode head2){
    LinkedListNode firstList = head1;
    LinkedListNode secondList = head2;
    LinkedListNode tmp = new LinkedListNode(0);
    LinkedListNode result = new LinkedListNode(0);
    int checkWhichList=0;
    if(firstList!=null && secondList!=null){
        if (firstList.getValue()<=secondList.getValue()){
            result.insert(result, secondList.getValue());
            secondList = secondList.getNext();
            checkWhichList++;
        }else{
            result.insert(result, firstList.getValue());
            firstList = firstList.getNext();
            //checkWhichList++;
        }
    }
    while(firstList!=null && secondList!=null) {
        if (checkWhichList % 2 != 0) {
            result.insert(result, firstList.getValue());
            firstList = firstList.getNext();
            checkWhichList++;
        } else{
            result.insert(result, secondList.getValue());
            secondList = secondList.getNext();
            checkWhichList++;
        }
    }
    if(firstList!=null){
        while(firstList!=null) {
            result.insert(result, firstList.getValue());
            firstList = firstList.getNext();
        }
    }
    if(secondList!=null){
        while(secondList!=null) {
            result.insert(result, secondList.getValue());
            secondList = secondList.getNext();
        }
    }
    //result.setNext(tmp);
    return result.getNext();
}
}
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 LinkedListNode insert(LinkedListNode head, int value){
        LinkedListNode temp = new LinkedListNode(value);
        LinkedListNode temp1 = head;
        if(head == null){
            return temp;
        }
        else{
            temp1 = head;
            while(temp1.next != null){
                temp1 = temp1.next;
            }
            temp1.next = temp;
        }
        return head;
    }
}