CODEWITHSUNDEEP
javalinked-list
user1371651
user1371651

Reputation: 23

Java Splitting integer Linked List

I need to write a method that starts with a single linked list of integers and a special value called the splitting value. The elements of the list are in no particular order. The method divides the nodes into two linked lists: one containing all the nodes that contain an element less than the splitting value and one that contains all the other nodes. If the original linked list had any repeated integers (i.e., any two or more nodes with the same element in them), then the new linked list that has this element should have the same number of nodes that repeat this element. The method returns two head references - one for each of the linked lists that were created.

I have been spent countless hours trying to get this right and think this is the closest but I have an error while compiling that my copyTail* IntNodes may not be initialized. I also may be completely wrong with my code.... Any help pointing in me in the right direction??

public static IntNode[ ] listSplitLessGreater(IntNode source, int splitter)
{
  IntNode copyHeadLess;
  IntNode copyTailLess;
  IntNode copyHeadGreater;
  IntNode copyTailGreater;
  IntNode[ ] answer = new IntNode[2];
    boolean less = true;
    boolean greater = true;

  // Handle the special case of the empty list.   
  if (source == null)
     return answer; // The answer has two null references .

  //Split list into two lists less and greater/equal than splitter.     
  while (source.link != null)
  {
    if (splitter < source.data)
        {
            if (less)
            {
            copyHeadLess = new IntNode(source.data, null);
            copyTailLess = copyHeadLess;
            less=false;
            }
            else
            {
            source = source.link;
            copyTailLess.addNodeAfter(source.data);
            copyTailLess = copyTailLess.link;

            }
        }
        else
        {
            if (greater)
            {
            copyHeadGreater = new IntNode(source.data, null);
            copyTailGreater = copyHeadGreater;
            greater=false;
            }
            else
            {
            source = source.link;
            copyTailGreater.addNodeAfter(source.data);
            copyTailGreater = copyTailGreater.link;

            }
        }

    }      

  //Return Head References
  answer[0] = copyHeadLess;
  answer[1] = copyHeadGreater;

  return answer;

}

Upvotes: 2

Views: 3082

Answers (2)

nvuono
nvuono

Reputation: 3363

If source isn't null, but source.link is null (list is only composed of one element) then you never assign to your copyHeadLess, etc, variables. Try initializing them to null or whatever the default is:

  IntNode copyHeadLess = null;
  IntNode copyTailLess = null; 
  IntNode copyHeadGreater = null; 
  IntNode copyTailGreater = null; 
  IntNode[ ] answer = new IntNode[2]; 
    boolean less = true; 
    boolean greater = true; 

  // Handle the special case of the empty list.    
  if (source == null) 
     return answer; // The answer has two null references . 

  //Split list into two lists less and greater/equal than splitter.      
  while (source.link != null) 
  { 
    // what about case where source isn't null but source.link is null?
  }       

  //Return Head References 
  answer[0] = copyHeadLess; // this may have never been assigned in your original code
  answer[1] = copyHeadGreater; // this may have never been assigned in your original code

  return answer; 

 }

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1500185

I think you're making it more complicated than it needs to be, by modelling a list just with a single class (IntNode). If you model it as "the list" and "a node in the list" then it's easy to have an empty list. You also don't need to keep track of both the head and the tail - the list can do that. At that point, it's very simple:

  • Create two empty lists, one for "lower" and one for "not lower"
  • Iterate over the original list:
    • Work out which list to add the element to
    • Add the element
  • Return both lists (e.g. using an array as you have done)

Note that even without that, you can make your code simpler by just using null to mean "I haven't got this list yet". At the moment your code won't compile, as copyHeadLess etc aren't definitely assigned when they're used. You know that you won't try to use them until they've been assigned, but the compiler doesn't. I'd still recommend the remodelling approach though :)

Upvotes: 3

Related Questions