Hi all
I am having a problem with my method in my linked list class to split linked lists into two sublists.
The issue is that for some reason my first sublist has 3 more elements than the second sublist when I split a linked list with a total of 17 elements.

Here is the code for the method:

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

Not entirely sure why it is not working but at least I got it so it actually splits the linked list LOL.

You've got a real design problem here, in the form of count. Count is a global, but clearly it's intended to represent the number of items in the sublist passed in as a parameter. What happens if I call this method with a list as a parameter, and that list doesn't have the right number of nodes? Second problem is this sets a global, "sublist" rather than returning the sublists (presumably as a Collection, which could be a list, of two root nodes).
So you need to review your logic, first of all.

Then, you could simplify this:

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

to this:

int subCount = (count+1)/2;
          for (int i = 0; i < subCount; i++)
          {
          current = current.link;
          }

As for your actual problem, are you sure that the value of count is correct coming in?

What about using a different method? Loop through the list with two counters, one of which advances two for each iteration, the other advances 1. When the first counter hits the end, your second counter should be right about where you want it, no? That way you don't have to keep track of count.

[EDIT : Spotted reading failure on my part. Disregard the part about sublist being a global, my bad ]

Edited 5 Years Ago by jon.kiparsky: n/a

Everything has to be in this particular method. As for the count....it should be correct coming in because it counts the number elements within the initial linked list.
In my method I tried doing subCount - 1 for the else portion that handles odd count of elements and it came out correctly. But then when I put in an even number of elements it gave the first sublist 2 more than the second sublist.

Okay, I think I see the problem.

Take a list of 8 items. subCount = 4, so we start at first, which is an item on the list. We start to walk through the list. After the first pass of the loop, we point to f.link. Second pass, f.link.link. Third, f.link.link.link. Fourth time- you see it now?

Not sure I entirely see what you mean yet.
Is the subCount the incorrect item in my method? Should I just have count/2 in even portion? and then for the odd portion perhaps count/2 + 1 for that for loop?

Actually I just tried that and it didn't work out. Stupid me. Well.....I understand somewhat of how the link point to each other. I mean using the subCount-1 in the for loop for the odd number of the if/else divides it properly but the even does not. This is very frustrating and leads me to believe that by adding the SubCount-1 for that particular for loop must not of really solved the issue at all for odd numbers.

This article has been dead for over six months. Start a new discussion instead.