5 Replies - 1073 Views - Last Post: 11 May 2011 - 10:28 AM Rate Topic: -----

#1 Vanya-234  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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)
    {
      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 :)

Is This A Good Question/Topic? 0
  • +

Replies To: Problem with splitting linked list

#2 japanir  Icon User is offline

  • jaVanir
  • member icon

Reputation: 1010
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 Vanya-234  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 japanir  Icon User is offline

  • jaVanir
  • member icon

Reputation: 1010
  • View blog
  • 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++)
          {
          current = current.link;
          }
        }
       else
        {
          for (int i = 0; i < subCount; i++)
          {
            current = current.link;
          }
        }



Was This Post Helpful? 0
  • +
  • -

#5 Vanya-234  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7762
  • View blog
  • Posts: 13,127
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1