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:
First List: 2 11 19 21 24
Second List: 14 15 18 23 25
Third List: 3 9 17 20 22
2 3 9 11 14 15 17 18 19 20 21 22 23 24 25
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
(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.
Merge K Sorted Linked Lists using Min Heap.
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.
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:
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).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With