# Sort and Merge Two Linked List

Printable View

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• February 27th, 2013, 09:55 PM
Norm
Re: Sort and Merge Two Linked List
Where is a copy made of the contents of the node?
The post code copies a reference to the one node to the other list. So of like this:
String aStr = "asdde";
String bStr = aStr;
bStr and aStr both point to the same String, there wasn't a copy made.

I'm done for tonight. Back tomorrow.
• February 27th, 2013, 10:03 PM
Loraeron
Re: Sort and Merge Two Linked List
So would you have to use something like

Node L3 = new Node();
L3.copy(L1.next);
• February 28th, 2013, 07:12 AM
Norm
Re: Sort and Merge Two Linked List
What would the copy() method do?
• February 28th, 2013, 08:53 AM
Loraeron
Re: Sort and Merge Two Linked List
It would perform a deep or shallow copy on the node passed and return it. Like when copying an object.
• February 28th, 2013, 09:12 AM
Norm
Re: Sort and Merge Two Linked List
So the copy() method would be in the linked list class and having nothing to do with the class???
It seems like it should be part of the Node class since it is working with Node data.
• February 28th, 2013, 12:29 PM
Loraeron
Re: Sort and Merge Two Linked List
Ok a new approach, i think we are adding to much to this method. I want to traverse List1 and List2 and compare them and sort at the same time by using simple comparison.
• February 28th, 2013, 12:40 PM
Norm
Re: Sort and Merge Two Linked List
Now you want to forget about the merge() method and work on another project?

You want to work with a method that will take two lists as input, sort each list and then merge the two lists and return the new, sorted list, leaving the original lists intact.
Back to the beginning. What are the steps this method must take to do each of those steps?
• February 28th, 2013, 12:47 PM
Loraeron
Re: Sort and Merge Two Linked List
No haha same project, different approach and it seems like this route would work better. Steps for this method:

TraverseList(List LL1, List LL2)
{

Node temp1 = LL1.next();
Node temp2 = LL2.next();

if(temp1 >= temp2)
{
LL3.add(temp2);
}
else
{
LL3.add(temp1);
}

}
• February 28th, 2013, 12:53 PM
Norm
Re: Sort and Merge Two Linked List
You need to work on the steps of the logic before trying to write code.
What values do the references to the Node objects have that are useful to the program?
Are the lists that are passed to the method already sorted?
What will the code do if the lists are not sorted?
By adding the nodes to the new list, they are removed from the old list.

What does the List class's next() method return?

Should there be a loop?
• February 28th, 2013, 06:19 PM
Loraeron
Re: Sort and Merge Two Linked List
I understand I was just throwing out a quit bit i thought about haha.

The list that are passed will be sorted, the traverseList method will perform another sort while merging them. I will have a helper point to each location in each list, it will compare the values, whichever is smaller will be placed into the new list, it will then increment the helper of the list that had the smaller value, and repeat until all elements have been merged (once it hits a null/tail pointer of either list) and placed into the right order.

I want to keep all the lists in tact so that I may show there before and after state.

The next() method returns the next node in the list.

I believe there will be a loop that keeps the traverse moving until it reaches the null/tail pointer of one of the lists passed as arguments.
• February 28th, 2013, 07:21 PM
Norm
Re: Sort and Merge Two Linked List
Quote:

The next() method returns the next node in the list.
How will that work? It sounds like what an iterator does.

You have got a lot more details of the new method now, but there still are some missing points.
What happens when the end of a list is found?

Quote:

traverseList method will perform another sort
Why? The lists are already sorted.
• February 28th, 2013, 08:00 PM
Loraeron
Re: Sort and Merge Two Linked List
i meant it to be the built in .next not a method i create shouldn't have placed the ().

When the end of one of the list is found it will jump to another if that says
if (LL01 == null)
{
LL03 = temp2;
temp2 = LL02.next;
}

keep in mind temp2 is established outside the if's, but inside a while that is traversing until both LinkedList register null.
Likewise if LL02 is null it will do the same operation only with temp1 and LL01.next.

Before it gets to the null pointers though since both list are sorted before going to the TraverseMerge it will run a comparison like below (I know you said no code, but its the only way i see to get this to be easily seen). My issue is with trying to figure out how to get the starting values into temp1 and temp2 from their respective list, otherwise i think this will work:

Code Java:

```public LinkedList TraverseMerge(LinkedList LL01, LinkedList LL02) {   LinkedList LL03 = null; //initialize the new merged list Node temp1 = ; //Holds current value of linked list 1 Node temp2 = ; //Holds current value of linked list 2   //Begin traversing both list while(LL01 != null && LL02 != null) {   //If the value in temp1 is greater than the value in temp2 place it into LL03 and move onto the next value in list 2 reloop if(temp1.value > temp2.value) { LL03.add(temp2); temp2 = LL02.next; } //If the value in temp2 is greater than the value in temp1 place it into LL03 and move onto the next value in list 1 reloop else if (temp2.value > temp1.value) { LL03.add(temp1); temp1 = LL01.next; } //We can perform the next else if and else because we know our list where sorted before being sent to the TraverseMerge //If temp1 is null, meaning the end of the list 1 has been reached add whatever value is in temp2 and move on to the next value in list2 and reloop else if (temp1 == null) { LL03.add(temp2); temp2 = LL02.next; } //If temp2 is null, meaning the end of the List 2 has been reached add whatever value is in temp1 and move on to the next value in list 1 and reloop else { LL03.add(temp1); temp1 = LL01.next } } }```
• February 28th, 2013, 08:03 PM
Norm
Re: Sort and Merge Two Linked List
What happens when you compile and execute the code?
• February 28th, 2013, 08:35 PM
Loraeron
Re: Sort and Merge Two Linked List
Well right now an error, because where i declare temp1 and temp2 right under LinkedList LL03 i don't assign anything because i'm stuck there. I need a way to retrieve the starting node of each list passed as an argument and i can't figure it out. I know i would need a method, something like:

Code Java:

```public Node linkStart(LinkedList LL) { Node startNode; if(LL != null) { startNode = LL.value; } return startNode; }```

I just don't know if that will actually work
Correct that I know it won't work because you can't use the .value with a list, it apparently only works on nodes. So that is the dilemma and i really don't have a clue how to get around it.
• February 28th, 2013, 08:38 PM
Norm
Re: Sort and Merge Two Linked List
Quote:

way to retrieve the starting node of each list
The linked list needs a couple of methods:
size() returns the # of nodes in the list
Node get(int) returns the node at int
• February 28th, 2013, 08:44 PM
Loraeron
Re: Sort and Merge Two Linked List
So.....:

Code Java:

```public int size() { int count = 0; Node ref = firstElement; while(ref != null) { count++; ref = ref.next }   return count; }   public void get(int) { return size(); }```
• February 28th, 2013, 08:46 PM
Norm
Re: Sort and Merge Two Linked List
Node get(int) returns the Node at the location passed as arg. You were looking for get(0)
• February 28th, 2013, 08:56 PM
Loraeron
Re: Sort and Merge Two Linked List
I'm still at a bit of a loss as to what would be inside the:

Code Java:

```public Node get(int x) { int searchLoc = x;       return foundNode; }```

how would this be linked to the list and size?
• February 28th, 2013, 09:03 PM
Norm
Re: Sort and Merge Two Linked List
Use a loop like in the size() method to find the Node at the requested location in the list.
• February 28th, 2013, 09:20 PM
Loraeron
Re: Sort and Merge Two Linked List
What do you think of this:

Code java:

```public Node get(int x) { int searchLoc = x; Node ref = firstElement; int counter = 0;   while(ref != null) { if(counter == searchLoc) { Node foundNode = ref; { }   return foundNode; }```
• February 28th, 2013, 09:23 PM
Norm
Re: Sort and Merge Two Linked List
Did you compile and test it to see if it works?
Call it with several different values.
• February 28th, 2013, 09:42 PM
Loraeron
Re: Sort and Merge Two Linked List
Here is the full code, the only error i'm getting is trying to use .next during my traverseMerge() method at the bottome

Code Java:

```package hw3_vinson; import java.util.LinkedList; 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 combintation of LL1 and LL2 HW3_Vinson LL3 = new HW3_Vinson();   //Print each list LL1.print(); LL2.print(); LL3.print(); }   //Node Class creation public class Node { public int element; public 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 public Node firstElement; public 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; } }   //Print out linked list public void print() { Node ref = firstElement; while (ref != null) { System.out.println(ref.element + " "); ref = ref.next; } }   public int size() { int count = 0; Node ref = firstElement; while(ref != null) { count++; ref = ref.next; }   return count; }   public Node get(int x) { int searchLoc = x; Node ref = firstElement; Node foundNode = null; int counter = 0;   while(ref != null) { if(counter == searchLoc) { foundNode = ref; } }   return foundNode; }   public HW3_Vinson TraverseMerge(HW3_Vinson LL01, HW3_Vinson LL02) { HW3_Vinson LL03 = new HW3_Vinson(); Node temp1 = LL01.get(0); Node temp2 = LL02.get(0);   while (LL01 != null && LL02 != null) { int temp2int = temp2.element; int temp1int = temp1.element; if(temp1int > temp2int) { LL03.add(temp2int); temp2 = LL02.next; } else if (temp2int > temp1int) { LL03.add(temp1int); temp1 = LL01.next; } else if (temp1 == null) { LL03.add(temp2int); temp2 = LL02.next; } else if (temp2 == null) { LL03.add(temp1int); temp1 = LL01.next; } }   return LL03; } }```
• February 28th, 2013, 09:45 PM
Norm
Re: Sort and Merge Two Linked List
Quote:

error i'm getting
Please copy the full text of the error message and paste it here.
• February 28th, 2013, 09:58 PM
Loraeron
Re: Sort and Merge Two Linked List
Nevermind, managed to clear the error, code will compile and run, but gets stuck in an endless loop when it enters the TraverseMerge() method and i'm not sure why:

Code Java:

```package hw3_vinson; import java.util.LinkedList; 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 combintation of LL1 and LL2 HW3_Vinson LL3 = new HW3_Vinson();   //Print each list LL1.print(); LL2.print(); LL3 = LL3.TraverseMerge(LL1, LL2); LL3.print(); }   //Node Class creation public class Node { public int element; public 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 public Node firstElement; public 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; } }   //Print out linked list public void print() { Node ref = firstElement; while (ref != null) { System.out.println(ref.element + " "); ref = ref.next; } }   public int size() { int count = 0; Node ref = firstElement; while(ref != null) { count++; ref = ref.next; }   return count; }   public Node get(int x) { int searchLoc = x; Node ref = firstElement; Node foundNode = null; int counter = 0;   while(ref != null) { if(counter == searchLoc) { foundNode = ref; } }   return foundNode; }   public HW3_Vinson TraverseMerge(HW3_Vinson LL01, HW3_Vinson LL02) { HW3_Vinson LL03 = new HW3_Vinson(); Node temp1 = LL01.get(0); Node temp2 = LL02.get(0);   while (LL01 != null && LL02 != null) { int temp2int = temp2.element; int temp1int = temp1.element; if(temp1int > temp2int) { LL03.add(temp2int); temp2 = temp2.next; } else if (temp2int > temp1int) { LL03.add(temp1int); temp1 = temp1.next; } else if (temp1 == null) { LL03.add(temp2int); temp2 = temp2.next; } else if (temp2 == null) { LL03.add(temp1int); temp1 = temp1.next; } }   return LL03; } }```
• February 28th, 2013, 10:08 PM
Norm
Re: Sort and Merge Two Linked List
Quote:

an endless loop when it enters the TraverseMerge() method
TIme for some debugging. Try debugging your code by adding println() statements to show execution progress and how variable values are changing. For example:
Add a: System.out.println("var=" + var);
after every line where a variable is changed by an assignment statement or where used to control looping.

I'm done for tonight. Back tomorrow.
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12