# Problem with splitting linked list

Page 1 of 1

## 5 Replies - 1393 Views - Last Post: 11 May 2011 - 10:28 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=231569&amp;s=800711cbc2e34bba23d159bccc6b3943&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Vanya-234

Reputation: 0
• Posts: 3
• Joined: 11-May 11

# Problem with splitting linked list

Posted 11 May 2011 - 07:27 AM

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)
{

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++)
{
}
}
else
{
for (int i = 0; i < subCount + 1; i++)
{
}
}

sublist.last = last;

last = current;

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.

Is This A Good Question/Topic? 0

## Replies To: Problem with splitting linked list

### #2 japanir

• jaVanir

Reputation: 1012
• Posts: 3,025
• Joined: 20-August 09

## Re: Problem with splitting linked list

Posted 11 May 2011 - 08:54 AM

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.

### #3 Vanya-234

Reputation: 0
• Posts: 3
• Joined: 11-May 11

## Re: Problem with splitting linked list

Posted 11 May 2011 - 09:01 AM

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.

### #4 japanir

• jaVanir

Reputation: 1012
• Posts: 3,025
• Joined: 20-August 09

## Re: Problem with splitting linked list

Posted 11 May 2011 - 09:41 AM

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++)
{
}
}
else
{
for (int i = 0; i < subCount; i++)
{
}
}

```

### #5 Vanya-234

Reputation: 0
• Posts: 3
• Joined: 11-May 11

## Re: Problem with splitting linked list

Posted 11 May 2011 - 09:45 AM

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.

### #6 jon.kiparsky

• Pancakes!

Reputation: 8739
• Posts: 15,049
• Joined: 19-March 11

## Re: Problem with splitting linked list

Posted 11 May 2011 - 10:28 AM

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

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }