Merging 3 linked lists into 1 (Java )

Question

I have a question for a final review for a coding class I am taking. It's asking to merge 3 linked lists into 1 linked list. The problem I am having is when merging the lists I am able to merge the three lists in ascending order but I am missing the last 2 nodes of the 2nd list 23 and 25. I cant figure out why it stops there. The question is here:

Write a program named LinkedTest that:

1. Creates three sorted singly linked lists of integers as shown below

First List:  2 11 19 21 24

Second List: 14 15 18 23 25

Third List:  3 9 17 20 22

2. Merges three linked lists into a new sorted linked list as show in the following: 2 3 9 11 14 15 17 18 19 20 21 22 23 24 25
3. Returns the new sorted linked list Requirement: your program must have a time complexity less than or equal to O(nlog n)

Here is my code:

public class LinkedTest {

public static class ListNode {

    private int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        next = null;
    }
}

ListNode head;

public static void main(String[] args) {

    LinkedTest list = new LinkedTest();

        int[] data1 = { 2, 11, 19, 21, 24 };

        ListNode head1 = new ListNode(data1[0]);

        for (int i = 1; i < data1.length; i++)
            list.push(head1, data1[i]);

        System.out.print("First List: ");
        list.display(head1);

        int[] data2 = { 14, 15, 18, 23, 25 };

        ListNode head2 = new ListNode(data2[0]);

        for (int count = 1; count < data2.length; count++)
            list.push(head2, data2[count]);

        System.out.println(" Second List: ") ;

        list.display(head2);

        int[] data3 = { 3, 9, 17, 20, 22 };

        ListNode head3 = new ListNode(data3[0]);

        for (int count = 1; count < data3.length; count++)
            list.push(head3, data3[count]);

        System.out.println(" Third List: ") ;

        list.display(head3);

        ListNode n = list.LinkedTest(head1, head2, head3);

        System.out.print(" Merged List: ");

        list.display(n);
    }



public ListNode LinkedTest(ListNode first, ListNode second, ListNode third) { 
      ListNode head = null;

        if (first == null && second != null && third != null)

            return second;

        else if (second == null && third != null && first != null)

            return third;

        else if (third == null && first != null && second != null)

            return first;

        else if (first.data < second.data && first.data < third.data) 
        {
            head = first;
            head.next = LinkedTest(first.next, second, third);
        } 
        else if (second.data < third.data && second.data < first.data)
        {
            head = second;
            head.next = LinkedTest(first, second.next, third);
        }

        else if (third.data < first.data && third.data < second.data)
        {
            head = third;
            head.next = LinkedTest(first, second, third.next);
        }

        return head;
    }

    public void push(ListNode head, int n) 
    {
        while (head.next != null)
            head = head.next;
        head.next = new ListNode(n);
    }

    public void display(ListNode head)
    {
        ListNode tempDisplay = head; 
        while (tempDisplay != null) 
        {
            System.out.print(tempDisplay.data);
            tempDisplay = tempDisplay.next; 
    }

    }
}

Output:

First List:   2 11 19 21 24 
Second List:  14 15 18 23 25 
Third List:   3 9 17 20 22 
Merged List:  2 3 9 11 14 15 17 18 19 20 21 22 24

Answer 1

Why limit yourself to 3-way merges? Let us look at the general case of N-way merging, and then apply that to 3-way (or plain old boring 2-way).

// drop-in replacement for your LinkedTest(), but I like the name better:
// ListNode n = list.merge(head1, head2, head3);
public ListNode merge(ListNode... nodes) {

    // find smallest, keep its index
    int firstIndex = -1;
    int firstValue = 0;
    for (int i=0; i<nodes.length; i++) {
        ListNode n = nodes[i];
        if (n != null && (firstIndex == -1 || n.data < firstValue)) {
            firstIndex = i;
            firstValue = n.data;
        }
    }

    if (firstIndex == -1) {
        // reached the end of all lists
        return null;
    } else {
        // use node with smallest as next head
        ListNode head = nodes[firstIndex];

        // call again with all lists, but skipping head
        // because we are already using it in the result list
        nodes[firstIndex] = head.next;
        head.next = merge(nodes);
        return head;
    }
}

You can look at this like a lot of chains with links that have numbers on them, where the numbers of each chain are in ascending order. To build a big chain with all numbers in order, you:

• grab all the small ends of the remaining chains
• choose the smallest link (if none remains, you have finished)
• take that link off its chain, and add it to the end of your new chain
• go back to choosing the smallest link of the old chains

In your answer, as Jacob_G has noted, you were missing some logic for choosing the correct smallest element when one or more lists were empty. Jacob's answer is fine, but I though I'd show you the bigger picture: if you understand it for N, 3 should be no stretch (plus, you gain insight on the general idea).