Thread: Sort and Merge Two Linked List

I am looking for help with a homework assignment that requires us to merge two linked list (integer type) and create a third list that is sorted without destroying the original list. I have created the code to get my first two linked list to display, and have the start of my merger method, but have hit a wall probably because of over thinking. I was hoping there was some easy way to append one linked list to another, but have had no such luck attempting this. A note on any assistance provided, please avoid using structs and pointers as we haven't really gotten into those yet and i don't feel at all confident with using them here especially since I'm still trying to figure out this whole linked list idea. Thank you in advance, and please try and edit my own code so it is easier for me to follow. Thanks.

package hw3_vinson;
import javax.xml.*;
 
public class HW3_Vinson 
{   
    public static void main(String[] args) 
    {
        //Linked list one holding integers
      HW3_Vinson LL1 = new HW3_Vinson();
      LL1.add(1);
      LL1.add(3);
      LL1.add(2);
 
       //Linked list two holding integers
      HW3_Vinson LL2 = new HW3_Vinson();
      LL2.add(4);
      LL2.add(8);
      LL2.add(5);
 
      //Will hold combination of LL1 and LL2
      HW3_Vinson LL3 = new HW3_Vinson();
 
      //Print each list
     LL1.print();
     LL2.print();
     LL3.print();
    }
 
    //Node Class creation
private class Node
{
    int element;
    Node next;
 
    Node(int el, Node n)
    {
        element = el;
        next = n;
    }
 
    Node(int el)
    {
        this(el, null);
    } 
}
 
//Set up nodes to store first and last element
private Node firstElement;
private Node lastElement;
 
//Constructor for class
public HW3_Vinson()
{
    firstElement = null;
    lastElement = null;
}
 
//check to see if list is empty, return null if true
public boolean isEmpty()
{
    return firstElement == null;
}
 
//add to end of list
public void add(int e)
{
    if (isEmpty())
    {
        firstElement = new Node(e);
        lastElement = firstElement;
    }
    else
    {
        lastElement.next = new Node(e);
        lastElement = lastElement.next;
    }
}
 
 
//Combine two linked list and return a new linked list NOTE: This code does not work, and I know that I can't
//use the .add method because it is for adding integers to a linked list.  I had tried to create another addList method
//but got no where with it.
/*
public Node mergeList(Node L1, Node L2)
{
    Node LL1 = L1;
    Node LL2 = L2;
    Node LL3 = null;
 
    while (LL1 != null)
    {
        LL3.add(LL1);
    }
 
    while (LL2 != null)
    {
        LL3.add(LL2);
    }
 
    return LL3;
}
*/
//Print out linked list
public void print()
{
    Node ref = firstElement;
    while (ref != null)
    {
        System.out.println(ref.element + " ");
        ref = ref.next;
    }
}
}

I did know there was a compile error, it was on my mergeList method I was tampering with. I have edited the above code and commented it out, should compile now. I was using NetBeans IDE, so you may have to save the file with the name HW3_Vinson before it will run.

Also in regards to your answer about appending the two list. How would I go about and specify the next pointer from one list to the first node of the other? Wouldn't that eliminate the first node of the second list?

Good point on the stucts and pointers I wasn't really thinking there haha, been using C++ some today to for other assignments.

Ideally I would want my merge method to be a standalone not inside one of the already existing lists. I would want it to take in two List arguments and return a list, but I just don't see how it is possible to do it that way. My other option would be to make the merge recreate both list by somehow accepting a two node arguments, and two int values (length of each list being passed), and return a new list containing all the nodes from both list: EX.

public List mergeList (Node List1, Node List2)
{
 
List1Node = List1;
List2Node = List2;
Node newList3 = null;
 
while (List1Node != null)
{
    newList3.add(List1Node);
}
 
while (List2Node != null)
{
   newList3.add(List2Node);
}
 
return newList3;
}

I know the above code is no where near right, but that is kind of what I'm envisioning occurring when the merge executes. Basically taking in the nodes of both list running through the first list until it hits the last position. All the while adding to the newList3, and then doing the same thing with List2. Then returning newList3 for sorting.

The initial list will not be sorted. Once the merged list is created then it will be sorted. The old list will still be available, I want to be able to show the two original list along with the third merged/sorted list, in other words i want the nodes in the new list to be copies of the old lists.

Merge code would need to accept two linked list arguments and return a linked list. If that can't be done i guess it will accept a Node and utilize the .next method built into java for linked list.

I assume by "What class defines the list?" you are asking what in my code is defining/creating the list. They are being made using the private class Node then in the main method by using the add method having elements attached to them. I'm just at a loss for how the method will accept two list arguments, is List variableName, a valid decleration for passing a list argument?

Still a bit unsure of what you mean, but i think you are asking what do i use to create my linked list and that would be HW3_Vinson. I have a constructor that initializes the list and then i'm manually filling them using the .add(xxx) method.

So would it be right then, that after both list are made and filled in the main method, make a call to the merge method ( mergeList(HW3_Vinson list) )?

The HW3_Vinson has a constructor for initial set up, then I have a Node class that is used to create pointers.

Yes the merge method will copy the two list and create a third, all the while leaving the two original list in tact. The merge method i believe would just be in the HW3_Vinson class like the other methods, add(), isEmpty(), etc.

I believe the merge method will need to accept one argument which would be a linked list and return a linked list.

Step 1: Send first linked list to merger
Step 2: Merger runs through the linked list it received and creates a new list (basically copying the list it received as an argument)
Step 3: Return the new linked list
Step 4: Call the merger again and send it the second linked list, this time though since our new linked list was created during Step 2 and 3 i would want it to append the items from the argument list to the new list. Question: Would I need two different merge methods to accomplish this?
Step 5: Return the new list with the items from the second list appended
Step 6: Run the new list through a sort for integers in ascending order.
Step 7: Display the two original list as well as the new third list sorted.

Haha ok, well I would set up a merge method that accepts two linked list arguments. Note List3 would be initialized in the main loop to null before calling the merge(List1, List2)

Step 1: Take the first linked list and run through it using the .next syntax with a while loop, and adds what it finds to a new linked list.

EX: while(List1 != null)
{
temp = List1.next;
List3.add(temp);
}

Step 2: Takes the second linked list and basically performs the same function as the above example except it would be:

EX: while(List2 != null)
{
temp = List2.next;
List3.add(temp);
}

Step 3: Return List3 (the newly created merged list)

Would I not need to initialize List3 outside of the method to be able to access it later? I then would use the merge to add to List3.

Also I assumed the two while loops where theoretically "creating copies" of the two passed linked list arguments and being stored into List3

Ok so if i return a LinkedList, List3, i will be able to access it like you would during a return of other methods?

By theoretically i meant it is copying, just not using a copy method instead I am trying to read the list and as it comes to each Node it places it into temp, which is then added to List3, it then repeats until it hits the null pointer.

I only have what i have written above which is:

Node temp = List1.next(); OR Node temp = List2.next();

then storing them into the new List3:

List3.add(temp);

I think that is what you where asking, i do not however have a separate copy method.

Question though, wouldn't it still be left in List1 and List2? Therefore it is basically making a copy. It is storing the data of the node in temp then applying it to List3.