[Vanya-234]

Hi all!
This is my first time posting to one of these things but here goes nothing.
I am having issues with one of my methods from my linked list class. It is just not splitting the list how it should.
Example: I enter 17 elements into this linked list and it was give the first sublist 3 more elements in it than the second. I will admit that an odd number of elements will give one list more than the other but it should only give the first list 1 more element than the second....not 3.

This is what my output looks like:
1 11 2 3 44 55 66 77 88 99 0 13 15 16 24 26 47
List 1:
1 11 2 3 44 55 66 77 88 99
Sublist:
0 13 15 16 24 26 47

The first set of numbers is the entire linked list of 17 elements.


Here is the code for the method in my linked list class:

public void splitMid(LinkedListClass<T> sublist)
    {
      LinkedListNode<T> current;
      
      if(count == 0)
      {
        System.out.println("List is Empty!");
      }
      else
      {
        current = first;
        int subCount = count/2;
        
       if(count%2 == 0)
        {
          for (int i = 0; i < subCount; i++)
          {
          current = current.link;
          }
        }
        else
        {
          for (int i = 0; i < subCount + 1; i++)
          {
            current = current.link;
          }
        }
          
          
        sublist.first = current.link;
        sublist.last = last;
        
       
        last = current;
        last.link = null;
        
        sublist.count = subCount;
      }             
    }

I was pretty sure that my if/else was correct in choosing how to divide based on if an even or odd number of elements were entered. However, I now believe I have made some simple error that now eludes me.
Thank you all for any help you can offer me

[japanir]

since you are assigning current the first element and then iterate subcount + 1 times (for odd count) you are actually assigning subcount + 2 elements in case of odd count (and subcount + 1 in case of even count).
The example you posted, count = 17.
therefore, subcount = 8.
if you assign first to current, you actually iterate 8 + 2 times = 10, and therefore linking 10 elements.
you have to iterate 1 less element.

[Vanya-234]

Well when I use subcount - 1 in my if else it helps with the odd number of elements but if I enter an even number of elements I get a problem because then it makes it so that the second sublist has 2 more elements than the first.
Ex:
1 2 3 4 5 6 7 8 9 0 11 22 33 44 55 66 77 88
List 1:
1 2 3 4 5 6 7 8 9 0
Sublist:
11 22 33 44 55 66 77 88

I can't imagine I've messed up my method that badly that it acts in this way. There must be simple solution I am overlooking.

[japanir]

You have an if\else ro handle the odd\even cases. so it is not the same code anyway.

        
       if(count%2 == 0)
        {
          for (int i = 0; i < subCount - 1; i++)
          {
          current = current.link;
          }
        }
       else
        {
          for (int i = 0; i < subCount; i++)
          {
            current = current.link;
          }
        }

[Vanya-234]

So the issue is with my if/else? or perhaps the lines of code within my if/else?
I was pretty sure the if/else was correct...it is even or else it is odd.
You can't really mess around with the current in each code can you?
This is pretty frustrating.

[jon.kiparsky]

First thing is to get rid of the if. You want to split at the midpoint. Based on your current logic, you want the main list to be greedy, so 5 splits 3 and 2. So to make that work, add one to count before you div to get subCount. (5+1)/2=3. Or set subCount=count-subCount. (5-(5/2)=3, 6-(6/2)=3). Now you don't have a branch in there, so you've cut your problems in half.

Then you can look at the logic by which you progress through the list. I think your real problem is that you're starting from first, rather than a root node. This logic should work fine, if you start from a root nodeinstead of starting from your first data item.

Of course, keeping track of a counter defeats some of the purpose of a linked list. Better to find a way to do this without a counter at all. There's one easy way, which you might call the tortoise-and-hare solution.(of course, this also requires a root node)

This post has been edited by jon.kiparsky: 11 May 2011 - 10:30 AM