• Post Reply Bookmark Topic Watch Topic
  • New Topic

Half/split a linked list in such a fashion  RSS feed

 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to split a singly linked list called "unsorted" into two lists left and right in such fashion that the odd nodes in "unsorted" will go to left and the even ones will go to right. After that, I want to delete those nodes in "unsorted", and I now have two separate lists: left and right.

I think I am stuck at my logics in the while loop. Before the while loop, I extract the first two nodes in the unsorted list and then delete them. The first the time the loop runs, I can extract the next two nodes in the unsorted list. But for the second time run, is left.next still pointing at the third node in the unsorted list? (Well, I already deleted the first two nodes but for the sake of my description, I need to say the third node so it is easy to describe my logics) If so, I did not successfully update my left and right linked lists, correct? Please give me some hints how to correctly update my left and right lists. Thank you.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Hugh,

question: do you have to use all this complex index juggling. risking null pointer exceptions?

If not:
a much simpler construction is: while 'unsorted' is not empty, remove the first node of 'unsorted',  and if a boolean 'gotoLeft' is true, add the value of that node to 'left', otherwise add that value to 'right'. Switch the boolean, and so on. This way, you let the already existing LinkedList class that you have do all the pointer updating.

If so: I'll have to look again at your code.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Piet,
Thank you for responding to my question. I have to use such a method to split my list. I am a newbie and I should stick to what I have learned so far even though it may be inefficient and annoying to you. If you need me to explain the logics how I approach my code, please let me know. Once again, I appreciate your time and your help.
Best,
Hugh
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, okay, using the complex variant.

First of all, and that is why I mentioned the risk of Null Pointer Exceptions: what if your list only has one element? Then 'unsorted.next' == null and so 'unsorted.next.next' will give an NPE.

Second: concerning the while-loop: what if temp.next == null? We then skip the while-loop. leaving temp for what it is.

Dealing with these possibilities makes the code quite complex.

But apart from that: the code looks okay. I agree with your suspicion though: after having updated the left- and right next-fields, it is time to update 'left' and 'right' themselves, like: left = left.next, et cetera.
That should work, I guess, but only decent testing will tell if you got it correct.

How do you test your code? Does 'Node' have a decent 'toString' method, so that you can easily print the Nodes? Can you single step to follow what happens for the first three or four nodes?
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is my complete code

 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Well, okay, using the complex variant.

First of all, and that is why I mentioned the risk of Null Pointer Exceptions: what if your list only has one element? Then 'unsorted.next' == null and so 'unsorted.next.next' will give an NPE.

Second: concerning the while-loop: what if temp.next == null? We then skip the while-loop. leaving temp for what it is.

if temp.next == null, it should be fine because at that point, I already got 3 nodes. I had a special case which handles the situations of one or no node.

Otherwise, I will have at least two nodes. I set temp = unsorted.next.next, so if temp.next == null, I already got more than two nodes to split. Am I right?
Thanks again!
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for using the code tags!

And sorry I forgot: welcome to the ranch!

And: the code is different that what I expected! So bear with me, it'll take me some  time to grasp it. One question did come to mind: what is the role of the two nodes 'first' and 'head'?
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I hope my drawing helps.
IMG_3596.jpeg
[Thumbnail for IMG_3596.jpeg]
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
public SortyList(int first, int ... rest)

I created a Constructor. It makes an instance of SortyList with one or more Node’s. The int in the first Node is first. The remaining Node’s have int’s from the array rest. This constructor uses Java syntax "...".
I hope this helps.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The head node later on is used to merge my two split lists. The whole project is as following:
1. Give an unsorted list.
2. Split them in half in the given fashion.
3. Sort each of them. Then merge them.
3a. Compare the first element in each list, whichever has the smaller value will be added to the merged list.
3b. If one of the lists is empty, then we will just add the the non-empty on to the merged list and return.
This algorithm is more efficient than divide and conquer.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I copied and ran your code. This line in 'main' gives an NPE!

Checking further...
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I ran my code and I agree.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hugh Winn wrote:The head node later on is used to merge my two split lists. The whole project is as following:
1. Give an unsorted list.
2. Split them in half in the given fashion.
3. Sort each of them. Then merge them.
3a. Compare the first element in each list, whichever has the smaller value will be added to the merged list.
3b. If one of the lists is empty, then we will just add the the non-empty on to the merged list and return.
This algorithm is more efficient than divide and conquer.

Makes sense, and I suggest concentrating on the first part, the splitting of the unsorted list. But wasn't that your original question? 
I must say, regarding item 3: I do not see how you handle this in your code, since that sounds like recursion. But that's probably me.

If I read your comments in the code, it is true that you are not allowed to create any new Node, not even for temporary use?
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are correct. I am not allowed to make any new node. But I can make a pointer left and right to make two new linked lists. ^^
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are correct again on part 3. I will use the recursive call sort(something) here.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm... these teachers sure know how to spoil one's day, don't they? 

Good news: the code runs for the first and the fourth line in 'main', bad news: it gives the NPE for the other four lines.

Going to look at the split of the list.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
They sure do. But I am having fun. I like challenge.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is code again with comments. Thanks.
 
Knute Snortum
Sheriff
Posts: 4281
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Hugh Winn:

At the CodeRanch, it's okay to crosspost, but you should be upfront about it.  That way we (at CodeRanch) don't waste our time it you are getting answers on another site.  You should also know that many sites consider crossposting to be bad etiquette.
 
Knute Snortum
Sheriff
Posts: 4281
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm still getting a NPE when I run this code.  Is that what you are getting?
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I apologize.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, that is what I am getting now. I did not update left and right properly.
 
Knute Snortum
Sheriff
Posts: 4281
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

How do you know that unsorted.next.next will exist or not be null?
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is a good point. If my list has two nodes, then temp will point to null. Should I make temp point to the second node of the unsorted list instead of the third one?
 
Knute Snortum
Sheriff
Posts: 4281
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wouldn't try to debug that method, I would rewrite it.  Piet had a good algorithm for you to use.  You should be able to describe what your splitting method does in less than ten sentences -- that is, not in any Java terms at all, just English.  Then create the code from those sentences.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But I am asked to use such a method to split my list.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hugh Winn wrote:. . . Should I make temp point to the second node of the unsorted list instead of the third one?
Whenever I see that sort of question, I start getting worried. That looks like somebody trying to sort out their logic problems in code; you shou‍ld have that sort of thing worked out before you try any coding. I think Knute means the same thing, but we have put it differently. You need another diagram like that earlier. But also please supply more details:-
  • Where is the head of the list and where is its end?
  • Is your list singly‑linked or doubly‑linked? I have an idea about that from looking at your code.
  • What handedness is the head node and what handedness is the end node?
  • Do you have a counter of how many Nodes you have? Can you use that counter to decide whether to mark a Node left or right? If you alternate it might be odd numbers=right, and even numbers=left, or similar.
  • Were you also trying to sort this List? What is going to happen to the handedness if you do sort it? Will you have to repeat the procedure of adding left and right?
  • Can you add left and right markers to each new Node as you populate the List?
  • I would go one further than PS and suggest you create yourself an enumerated type, with a suitable name and two elements (would you believe, LEFT and RIGHT). You can give each a method like getOther so LEFT returns RIGHT and vice versa.

    Is the idea behind splitting this list so you can do some sort of merge sort on it? You can divide a linked list into two Lists quite easily without such markers, but there is the possibility that you will divide it into two lists running backwards.
     
    Aidan Johansson
    Ranch Hand
    Posts: 32
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I want to alternately split the give singly linked list, sort both of the new lists and then merge them. This sorting algorithm is supposed be efficient.
    The head right now is pointing to null. It will be used later on to merge two sorted linked lists.
     
    Campbell Ritchie
    Marshal
    Posts: 56570
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hugh Winn wrote:. . . This sorting algorithm is supposed be efficient. . . .
    Not convinced. In order to do efficient sorting, you are going to have to subdivide your List into so many Lists that you can be sure each List has nothing out of order. Without sorting, the largest possible List with no elements out of order has one element in. So you are going to have to do a lot of subdividing. Unless you have been told specifically to use that technique, read this. [Sorry, wrong link: try this instead.] Also please search this forum; I gave the same link to somebody else earlier today.

    What you described about sorting does sound like a merge sort.
     
    Knute Snortum
    Sheriff
    Posts: 4281
    127
    Chrome Eclipse IDE Java Postgres Database VI Editor
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hugh Winn wrote:But I am asked to use such a method to split my list.

    I'm having trouble understanding this sentence.  You are writing this sort method, correct?  Can't you write anything you choose in that method?  If so, I would encourage you to write down in English (or your first language) how you plan to do this.  Each step should be clear and simple and unambiguous.  Sometimes pretending that you're explaining the process to a 10 year old helps.  Don't use any Java terms.  Once you have this "explanation," called an algorithm, use it to create your code.
     
    Aidan Johansson
    Ranch Hand
    Posts: 32
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It works now. Thanks everyone.
     
    Campbell Ritchie
    Marshal
    Posts: 56570
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well done sorting it Do tell us how you managed that.
     
    Aidan Johansson
    Ranch Hand
    Posts: 32
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Step 1: To half into two lists: left and right and add the nodes to the front of these lists.
     
    Campbell Ritchie
    Marshal
    Posts: 56570
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    There must be a more elegant way to do that than while (true)...
     
    Aidan Johansson
    Ranch Hand
    Posts: 32
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That was all I could think of.
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Excuses for the unexpected delay.

    There are two big problems with splitting the list into two parts: retaining the references of the left and the right part, and, if the list has more than three Nodes, geting the last-but one Node correct, in that last-but-one.next must be null, instead of pointing to the last Node. I could only solve that problem in a somewhat elegant fashion by creating a new Node, equal to the current Node, but with the next field equal to null.
    So I added this Node constructor:

    and the splitting itself goes like:
       
    Apart from refactoring, this is horrible code! It is very complex to get it right, and it is hard to follow. Compare that with this code (assuming correct constructors):
     
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hugh Winn wrote:It works now. Thanks everyone.

    Can you show us the full working code? My code sorts fine, but it did not meet exactly the requirements of not introducing extra Nodes. I'd love to see how you coped with that. Thanks!
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!