Merging two linked lists alternately while looking for a maximum as the head

Question

I'm working on a linked-list program, which allows me to loop over the list only once, and I can't copy the elements of the list to another data structure.

Suppose that the list is not empty (has at least one node) and the next of the last node is null.

The following method is supposed to merge two linked lists, the head of the merged list should be the maximum value in both lists. The following values are alternating between the two lists.

For example if my input is :

1 2 4 

3 5 6 7 8 9

my output would be :

3 1 5 2 6 4 7 8 9

I figured out how to assign the head, but I can't figure out how to merge he rest of the list properly.

This is my code:

    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

Once you determine which Node has the maximum value you have to add both heads to result (maximum value first) then move your pointers of firstList and secondList

Now, you continue adding to result from both lists while moving to the next Node on each until both are not pointing to anything

Example: (taking the case when firstList is the head)

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

You can try this code:

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