Sort and Merge Two Linked List

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• February 26th, 2013, 19:15
Loraeron
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.

Code java:

```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; } } }```
• February 26th, 2013, 19:34
Norm
Re: Sort and Merge Two Linked List
Quote:

easy way to append one linked list to another
Set the next pointer at the end of one linked list to the first node in the other linked list.

Quote:

please avoid using structs and pointers
That will be easy. There are none in java.

The posted code has compiler errors. Do you get compiler errors?
Please copy and paste the full text of any error messages here.
• February 26th, 2013, 19:53
Loraeron
Re: Sort and Merge Two Linked List
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.
• February 26th, 2013, 20:05
Norm
Re: Sort and Merge Two Linked List
Quote:

next pointer from one list to the first node
The node at the end of the first list would be connected to the first node of the second list.
Take a piece of paper and draw some nodes for two lists. Connect the nodes in each list with a line representing the next pointer. The next pointer in last node of a list would be empty. To connect the lists, draw a line from the end of one to the start of the other.

You need to think about what the merge() method do before writing the code.
What class would it be in? Would it be in one of the lists to be merged?
What would it take as parameters and what it would return?
Will it create copies of all the nodes from the two lists or will it use the existing nodes and destroy the two lists?
• February 26th, 2013, 20:49
Loraeron
Re: Sort and Merge Two Linked List
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.
Code Java:

```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.
• February 26th, 2013, 20:57
Norm
Re: Sort and Merge Two Linked List
Are the lists sorted? Does their order matter when the lists are merged?

Will the old lists be lost when the new list is created or will the nodes in the new list be copied from the old lists?

Forget about writing any code until you have a design for what the new method is going to do.
Paper and pencil are useful when working with linked list design.
• February 26th, 2013, 21:46
Loraeron
Re: Sort and Merge Two Linked List
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.
• February 26th, 2013, 21:56
Norm
Re: Sort and Merge Two Linked List
Ok. Make a list of the steps the merge code needs to do. It needs to include what args it will get when it is called and what it will return.

It sounds like the merge is just a connecting together of two lists.

I'm done for tonight. Back tomorrow.
• February 27th, 2013, 06:34
Loraeron
Re: Sort and Merge Two Linked List
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.
• February 27th, 2013, 07:23
Norm
Re: Sort and Merge Two Linked List
Ok, start with that: the method takes two lists as input and returns a new list. What class defines the list?
Then what does the method do?
• February 27th, 2013, 08:14
Loraeron
Re: Sort and Merge Two 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?
• February 27th, 2013, 08:23
Norm
Re: Sort and Merge Two Linked List
Sorry, that was poorly worded. What is the name of the linked list class the code will be using?
You will need that to define a method that takes list objects as arguments.
• February 27th, 2013, 17:45
Loraeron
Re: Sort and Merge Two Linked List
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) )?
• February 27th, 2013, 18:24
Norm
Re: Sort and Merge Two Linked List
Some class defines the methods of the linked list and holds the pointers to the nodes in the list.
What is the name of that class? Is it HW3_Vinson?

I'm still not sure what the merge method does with the two lists? Is it: copying the nodes from both lists and making a new list with those copied nodes? If that is what it is supposed to do, have you made a list of the steps the method must do to do it?
What class would the merge() method be in?
If the merge() method does something else, please explain.
• February 27th, 2013, 18:55
Loraeron
Re: Sort and Merge Two Linked 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.
• February 27th, 2013, 19:03
Norm
Re: Sort and Merge Two Linked List
That design seems a bit awkward. I'd have the method do the merge in one step.

Step 2 needs some expansion to list the steps required. The way it's worded, it sounds like a clone() method that creates a copy of the list that was passed to it.

Step 4 is weird. Its a hybrid of Step 2 and the actual merge. ???

Steps 6 & 7 are not part of the merge() method.

Basically I'd start over with the design.
• February 27th, 2013, 19:49
Loraeron
Re: Sort and Merge Two Linked List
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;
}

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

Step 3: Return List3 (the newly created merged list)
• February 27th, 2013, 19:55
Norm
Re: Sort and Merge Two Linked List
The "create a copy" step is missing.

Why is List3 created outside of the merge() method?
• February 27th, 2013, 20:06
Loraeron
Re: Sort and Merge Two Linked 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
• February 27th, 2013, 20:10
Norm
Re: Sort and Merge Two Linked List
Quote:

to be able to access it later
I thought that it was returned by merge(). merge() creates it, fills it and returns it.

Quote:

theoretically "creating copies"
The more details covered in the design, the fewer problems when writing the code.
• February 27th, 2013, 20:19
Loraeron
Re: Sort and Merge Two Linked List
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.
• February 27th, 2013, 20:25
Norm
Re: Sort and Merge Two Linked List
Do you have the steps for making a copy of a node?
• February 27th, 2013, 20:28
Loraeron
Re: Sort and Merge Two Linked List
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: