Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 2 of 2 FirstFirst 12
Results 26 to 50 of 50

Thread: Sort and Merge Two Linked List

  1. #26
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  2. #27
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    So would you have to use something like

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

  3. #28
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    What would the copy() method do?
    If you don't understand my answer, don't ignore it, ask a question.

  4. #29
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  5. #30
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #31
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  7. #32
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  8. #33
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    }

  9. #34
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  10. #35
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  11. #36
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    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?

    traverseList method will perform another sort
    Why? The lists are already sorted.
    If you don't understand my answer, don't ignore it, ask a question.

  12. #37
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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:

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

  13. #38
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    What happens when you compile and execute the code?
    If you don't understand my answer, don't ignore it, ask a question.

  14. #39
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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:

    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.

  15. #40
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    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
    If you don't understand my answer, don't ignore it, ask a question.

  16. #41
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

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

  17. #42
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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)
    If you don't understand my answer, don't ignore it, ask a question.

  18. #43
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

    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?

  19. #44
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  20. #45
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sort and Merge Two Linked List

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

  21. #46
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    Did you compile and test it to see if it works?
    Call it with several different values.
    If you don't understand my answer, don't ignore it, ask a question.

  22. #47
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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

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

  23. #48
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    error i'm getting
    Please copy the full text of the error message and paste it here.
    If you don't understand my answer, don't ignore it, ask a question.

  24. #49
    Member
    Join Date
    Feb 2013
    Location
    Georgia
    Posts
    44
    My Mood
    Fine
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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:

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

  25. #50
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,414
    Thanks
    49
    Thanked 2,214 Times in 2,187 Posts

    Default Re: Sort and Merge Two Linked List

    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.
    If you don't understand my answer, don't ignore it, ask a question.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. heap sort vs merge sort
    By IHeartProgramming in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 3rd, 2012, 03:37 AM
  2. [SOLVED] displaying every 1000 comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 6
    Last Post: May 27th, 2012, 07:26 PM
  3. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 26th, 2012, 11:54 PM
  4. Insertion Sort on a Doubly Linked List
    By Kaisshau in forum What's Wrong With My Code?
    Replies: 4
    Last Post: June 7th, 2011, 11:18 PM
  5. Pseudo code of insertion sort linked list
    By sungirl in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 23rd, 2010, 09:25 AM

Tags for this Thread