Thread: Sort and Merge Two Linked List

So would you have to use something like

Node L3 = new Node();
L3.copy(L1.next);

It would perform a deep or shallow copy on the node passed and return it. Like when copying an object.

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.

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

}

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.

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:

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

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:

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.

So.....:

public int size()
{
int count = 0;
Node ref = firstElement;
    while(ref != null)
    {
        count++;
        ref = ref.next
    }
 
return count;
}
 
public void get(int)
{
    return size();
}

I'm still at a bit of a loss as to what would be inside the:

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

how would this be linked to the list and size?

What do you think of this:

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

Here is the full code, the only error i'm getting is trying to use .next during my traverseMerge() method at the bottome

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

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:

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