Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Merging 3 linked lists into 1 (Java )

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
  1. 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
  2. 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
like image 894
Daniel Rogers Avatar asked Dec 19 '18 02:12

Daniel Rogers


People also ask

How do you combine linked lists?

(1) Create a new head pointer to an empty linked list. (2) Check the first value of both linked lists. (3) Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node. (4) Continue this process until you reach the end of a linked list.

Which data structure can be used to optimally merge K singly linked lists?

Merge K Sorted Linked Lists using Min Heap.

What is the linked list?

A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.


1 Answers

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).

like image 151
tucuxi Avatar answered Sep 19 '22 05:09

tucuxi