Half/split a linked list in such a fashion

[Aidan Johansson]

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.

if(unsorted == null)
    {
        return unsorted;
    }
    else {
        Node temp = unsorted.next.next;
        Node left = unsorted;
        Node right = unsorted.next;
        left.next = null;
        right.next = null;
        unsorted = temp;
        while (temp.next != null) {
            left.next = temp;
            right.next = temp.next;
            left.next.next = null;
            right.next.next = null;
            temp = temp.next.next;
            unsorted = temp;
        }
    }

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]

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]

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]

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]

Here is my complete code

class SortyList
{

//  NODE. A node in a singly linked linear list of INT's.

    private class Node
    {
        private int  key;   //  The INT.
        private Node next;  //  The next NODE in the list, or NULL.

//  Constructor. Make a NODE with KEY and NEXT.

        private Node(int key, Node next)
        {
            this.key  = key;
            this.next = next;
        }
    }

    private Node head;   //  Head NODE.
    private Node first;  //  First NODE in a list of NODEs.

//  SORTY LIST. Constructor. Make a list of NODEs that holds the INT arguments.
//  Also make a HEAD node for SORT to use.

    public SortyList()
    {
        head = new Node(0, null);
    }

    public SortyList(int first, int ... rest)
    {
        Node last = new Node(first, null);
        this.first = last;
        for (int index = 0; index < rest.length; index += 1)
        {
            last.next = new Node(rest[index], null);
            last = last.next;
        }
        head = new Node(0, null);
    }

//  SORT. Sort the list whose first NODE is FIRST. We can't make more NODEs but
//  we can change the NEXT slots of the existing NODEs.

    public SortyList sort()
    {
        first = sort(first);
        return this;
    }

//  Sort the list UNSORTED without making any new NODE's, and return the sorted
//  list.

    private Node sort(Node unsorted)
    {

        if(unsorted == null)
        {
            return unsorted;
        }
        else {
            Node temp = unsorted.next.next;
            Node left = unsorted;
            Node right = unsorted.next;
            left.next = null;
            right.next = null;
            unsorted = temp;
            while (temp.next != null) {
                left.next = temp;
                right.next = temp.next;
                left.next.next = null;
                right.next.next = null;
                temp = temp.next.next;
                unsorted = temp;
            }
            if (left == null || left.next == null) {
                return left;
            }
            if (right == null || right.next == null) {
                return right;
            } else {
                if (left.key <= left.next.key) {
                    sort(left.next);
                }
                if (right.key <= right.next.key) {
                    sort(right.next);
                }
            }
            while (left != null || right != null) {
                if (left != null && right != null) {
                    if (left.key < right.key) {
                        head.next = left;
                        left = left.next;
                    } else {
                        head.next = right;
                        right = right.next;
                    }
                    head = head.next;
                } else if (left == null) {
                    head.next = right;
                    break;
                } else if (right == null) {
                    head.next = left;
                    break;
                }
            }
        }
        return head.next;
    }


//  TO STRING. Turn FIRST into a string for printing. If the list is empty then
//  the string is "[]". Otherwise it's "[K₁, K₂ ..., Kⱼ]" where the K's are the
//  KEYS from FIRST, in order of appearance.

    public String toString()
    {
        StringBuilder builder = new StringBuilder();
        builder.append('[');
        if (first != null)
        {
            Node temp = first;
            builder.append(temp.key);
            temp = temp.next;
            while (temp != null)
            {
                builder.append(", ");
                builder.append(temp.key);
                temp = temp.next;
            }
        }
        builder.append(']');
        return builder.toString();
    }

//  MAIN. Test SORTY LIST by running it on a few examples.

    public static void main(String[] args)
    {
        System.out.println(new SortyList()                            .sort());
        System.out.println(new SortyList(0)                           .sort());
        System.out.println(new SortyList(1, 0)                        .sort());
        System.out.println(new SortyList(2, 1, 0)                     .sort());
        System.out.println(new SortyList(9, 8, 7, 6, 5, 4, 3, 2, 1, 0).sort());
        System.out.println(new SortyList(5, 8, 4, 9, 0, 1, 2, 3, 7, 6).sort());
    }
}

[Aidan Johansson]

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.

if(unsorted == null || unsorted.next == null)
        {
            return unsorted;
        }

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]

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]

I hope my drawing helps.

[Aidan Johansson]

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]

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]

I copied and ran your code. This line in 'main' gives an NPE!

System.out.println(new SortyList(0).sort());

Checking further...

[Aidan Johansson]

I ran my code and I agree.

[]
[0]
Exception in thread "main" java.lang.NullPointerException
	at SortyList$Node.access$100(nguy2952_Project2.java:6)
	at SortyList.sort(nguy2952_Project2.java:69)
	at SortyList.sort(nguy2952_Project2.java:48)
	at SortyList.main(nguy2952_Project2.java:146)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

[Piet Souris]

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]

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]

You are correct again on part 3. I will use the recursive call sort(something) here.

[Piet Souris]

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]

They sure do. But I am having fun. I like challenge.

[Norm Radder]

Also posted at:  http://www.dreamincode.net/forums/topic/403228-halfsplit-a-linked-list/
and https://www.java-forums.org/new-java/97157-split-linked-list-into-two-such-fashion.html
and http://forums.codeguru.com/showthread.php?559179-Half-split-a-linked-list-in-such-a-fashion

[Aidan Johansson]

Here is code again with comments. Thanks.

class SortyList
{

//  NODE. A node in a singly linked linear list of INT's.

    private class Node
    {
        private int  key;   //  The INT.
        private Node next;  //  The next NODE in the list, or NULL.

//  Constructor. Make a NODE with KEY and NEXT.

        private Node(int key, Node next)
        {
            this.key  = key;
            this.next = next;
        }
    }

    private Node head;   //  Head NODE.
    private Node first;  //  First NODE in a list of NODEs.

//  SORTY LIST. Constructor. Make a list of NODEs that holds the INT arguments.
//  Also make a HEAD node for SORT to use.

    public SortyList()
    {
        head = new Node(0, null);
    }

    public SortyList(int first, int ... rest)
    {
        Node last = new Node(first, null);
        this.first = last;
        for (int index = 0; index < rest.length; index += 1)
        {
            last.next = new Node(rest[index], null);
            last = last.next;
        }
        head = new Node(0, null);
    }

//  SORT. Sort the list whose first NODE is FIRST. We can't make more NODEs but
//  we can change the NEXT slots of the existing NODEs.

    public SortyList sort()
    {
        first = sort(first);
        return this;
    }

//  Sort the list UNSORTED without making any new NODE's, and return the sorted
//  list.

    private Node sort(Node unsorted)
    {
        if(unsorted == null || unsorted.next == null)
        {
            return unsorted;
        }
        // Here, I try to split the list "unsorted into" two lists: left and right in such a fashion that
        // the odd nodes in "unsorted" will go to the left list and the even ones will go to the right list.
        //At the end, all nodes in unsorted will be deleted. I will have two unsorted lists: left and right.
        else {
        // I create a temp variable that points to the third node in the "unsorted" list.
            Node temp = unsorted.next.next;
        // I create a left variable that points to the first node in the "unsorted" list.
            Node left = unsorted;
        // I create a right variable that points to the second node in the "unsorted" list.
            Node right = unsorted.next;
        // Lines 71 and 72 are saying that I want to extract the first two nodes in the "unsorted" list
        // and then delete them from that list.
            left.next = null;
            right.next = null;
        // I re-assign the unsorted pointer to point to where temp is point to right now,
        // which is the third node in the orginal "unsorted" list, or I would say the first node
        // in the "new" unsorted list after I extracted the first two nodes in the orignal one.
            unsorted = temp;
         // I now use a while loop to walk through the rest of the list and extract each node in the
         // "unsorted" list in the given fashion.
            while (temp.next != null) {
                // For the first time the loop runs, I assign left.next to point to where temp points to right now,
                // which is the first node in the "unsorted" list. Then at this point, I need to make left.next.next points to null
                // so I can have a list "left" with two nodes and at the end, there is a null element.
                left.next = temp;
                left.next.next = null;
                // For the first time the loop runs, I assign right.next to point to where temp.next points to right now,
                // which is the second node in the "unsorted" list. Then at this point, I need to make right.next.next points to null
                // so I can have a list "right" with two nodes and at the end, there is a null element.
                right.next = temp.next;
                right.next.next = null;
                // As usual, I need to delete the nodes I just moved to the left and right lists, so line 94 and 95 delete the first two nodes in
                // the "unsorted" list by re-assigning temp and unsorted.
                temp = temp.next.next;
                unsorted = temp;
            }

            // I am sorting two lists left and right by recursively calling the "sort" method I am writing
            // If the left list is empty or has one element, then I do not have to sort at all. I just return the whole list.
            if (left == null || left.next == null) {
                return left;
            }
            // If the right list is empty or has one element, then I do not have to sort at all. I just return the whole list.
            else if (right == null || right.next == null) {
                return right;
            }
            //Otherwise...
            else {
                if (left.key <= left.next.key) {
                    sort(left.next);
                }
                if (right.key <= right.next.key) {
                    sort(right.next);
                }
            }

            //After succesfully halfing the "unsorted" list and sorting two left and right lists, I merge them into one by using the head node.
            while (left != null || right != null)
            {
            // Merging two lists in such a fashion that compare the first two elements in each list, whichever smaller is put into the merged list.
                if (left != null && right != null)
                {
                    if (left.key < right.key) {
                        head.next = left;
                        left = left.next;
                    } else {
                        head.next = right;
                        right = right.next;
                    }
                    head = head.next;
                }
                // Recall that when we split two lists, we may have two list of the same number of elements or one is larger that another. Lines 134-141
                // make sure whatever list goes empty first, we will merge the rest of the non-empty list to the merged list as it is already sorted.
                else if (left == null) {
                    head.next = right;
                    break;
                }
                else if (right == null) {
                    head.next = left;
                    break;
                }
            }
        }
        return head.next;
    }


//  TO STRING. Turn FIRST into a string for printing. If the list is empty then
//  the string is "[]". Otherwise it's "[K₁, K₂ ..., Kⱼ]" where the K's are the
//  KEYS from FIRST, in order of appearance.

    public String toString()
    {
        StringBuilder builder = new StringBuilder();
        builder.append('[');
        if (first != null)
        {
            Node temp = first;
            builder.append(temp.key);
            temp = temp.next;
            while (temp != null)
            {
                builder.append(", ");
                builder.append(temp.key);
                temp = temp.next;
            }
        }
        builder.append(']');
        return builder.toString();
    }

//  MAIN. Test SORTY LIST by running it on a few examples.

    public static void main(String[] args)
    {
        System.out.println(new SortyList()                            .sort());
        System.out.println(new SortyList(0)                           .sort());
        System.out.println(new SortyList(1, 0)                        .sort());
        System.out.println(new SortyList(2, 1, 0)                     .sort());
        System.out.println(new SortyList(9, 8, 7, 6, 5, 4, 3, 2, 1, 0).sort());
        System.out.println(new SortyList(5, 8, 4, 9, 0, 1, 2, 3, 7, 6).sort());
    }
}

[Knute Snortum]

Norm Radder wrote:Also posted at:  http://www.dreamincode.net/forums/topic/403228-halfsplit-a-linked-list/
and https://www.java-forums.org/new-java/97157-split-linked-list-into-two-such-fashion.html
and http://forums.codeguru.com/showthread.php?559179-Half-split-a-linked-list-in-such-a-fashion

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]

I'm still getting a NPE when I run this code.  Is that what you are getting?
[] Exception in thread "main" [0] java.lang.NullPointerException at SortyList$Node.access$2(SortyList.java:9) at SortyList.sort(SortyList.java:81) at SortyList.sort(SortyList.java:48) at SortyList.main(SortyList.java:178)

[Aidan Johansson]

I apologize.

[Aidan Johansson]

Yes, that is what I am getting now. I did not update left and right properly.

[Knute Snortum]

       // I create a temp variable that points to the third node in the "unsorted" list.            Node temp = unsorted.next.next;
How do you know that unsorted.next.next will exist or not be null?

[Aidan Johansson]

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]

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]

But I am asked to use such a method to split my list.

[Campbell Ritchie]

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]

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]

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]

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]

It works now. Thanks everyone.

[Campbell Ritchie]

Well done sorting it Do tell us how you managed that.

[Aidan Johansson]

Step 1: To half into two lists: left and right and add the nodes to the front of these lists.

while (true) {
            if (unsorted != null) {
                currNode = unsorted.next;
                unsorted.next = left;
                left = unsorted;
                unsorted = currNode;
            } else {
                break;
            }
            if (unsorted != null) {
                currNode = unsorted.next;
                unsorted.next = right;
                right = unsorted;
                unsorted = currNode;
            } else {
                break;
            }
        }

[Campbell Ritchie]

There must be a more elegant way to do that than while (true)...

[Aidan Johansson]

That was all I could think of.

[Piet Souris]

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:

private Node(int key) {
    this.key = key;
    this.next = null;
}

and the splitting itself goes like:

private Node sort(Node startNode) {
        if (startNode == null || startNode.next == null) return startNode;
        Node currentNode = startNode.next.next;
        Node left = startNode;
        Node right = startNode.next;
        left.next = null; 
        right.next = null;
        Node currentLeft = left, currentRight = right;
        boolean gotoLeft = true;
        while (currentNode != null) {
            Node temp = new Node(currentNode.key);
            if (gotoLeft) {
                currentLeft.next = temp;
                currentLeft = temp;
            }
            else {
                currentRight.next = temp;
                currentRight = temp;
            }
            gotoLeft = !gotoLeft;
            currentNode = currentNode.next;
        }
        
        left = sort(left);
        right = sort(right);
        // and merging left and right
    }

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

public void sort() {
        if (head == null || head.next == null) return;
        SortyList left = new SortyList(), right = new SortyList();
        boolean gotoLeft = true;
        Node currentNode = head;
        while (currentNode != null) {
            if (gotoLeft) {
                left.add(currentNode.key);
            }
            else {
                right.add(currentNode.key);
            }
            gotoLeft = !gotoLeft;
            currentNode = currentNode.next;
        }
        left.sort();
        right.sort();
        head = left.merge(right).head;
    }

[Piet Souris]

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!