Singly Linked List "Strange sorting" exercise

Question

I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there.

One of these involves taking a singly linked list (type not specified) and rearranging the nodes. The sorting involves first having all nodes appear that were at "even" positions in the prior linked list and after that having all nodes appear that were at "uneven" positions in the prior linked list. All this while every node should keep their relative position. I chose to write this for a linked list with a null reference at its tail and a true node as head.

So short example: a list of values 4-5-7-3-2-1-null should rearrange to 4-7-2-5-3-1-null.

I wrote some code that worked (the strangeSort (Node x) method) but can't think of it as an elegant solution. I am convinced that there must be a way out there to make this neater, especially the for-loop in the strangeSort method. Base idea behind it was to make the original linked list basically 2 linked lists with different head nodes and then attaching one linked list at the end of the other.

The code:

public class Test {
    static class Node
    {
        int val; Node next;
        Node(int v){val=v;}
    }

    public static void main (String[] args)
    {
        /*Create Linked list of length N*/
        int N=Integer.parseInt(args[0]);
        Node head = new Node(0);
        Node x = head, x2;
        for (int i=1; i<N; i++, x = x2)
        {
            x2 = new Node(i);
            x.next = x2;
        }

        /*Prints out linked list for checking purposes*/
        for (Node t = head; t!=null; t=t.next)
        {   
            System.out.print(t.val+" -> ");
        }

        /*Rearrange Linked list*/
        strangeSort(head);

        /*Prints out linked list after sorting for checking purposes*/
        System.out.println();
        for (Node t = head; t!=null; t=t.next)
        {   
            System.out.print(t.val+" -> ");
        }

    }

    public static void strangeSort (Node x)
    {
        Node headu = x, heade = x.next;
        Node t,s;
        for (t=headu, s=heade ; t!=null && s!=null ; t=t.next , s=s.next)
        {
            if (t.next==null){break;}
            t.next = t.next.next;
            if (s.next ==null){break;}
            s.next = s.next.next;
        }
        if (t==null){t=heade;}
        else if (t.next==null){t.next = heade;}
    }
}

As you can see, the forloop of strangeSort contains a fairly inelegant way to make sure I don't get a NullPointerException in the end through the fact that I am traversing 2 nodes every iteration of the loop.

Answer 1

Interesting exercise.

I think you missed an easy solution to it which I'll get to, but a code-review first...

Vertical whitespace is a critical part of the readability of code... and you are missing a lot of it. Code like:

    if (t.next==null){break;}
    t.next = t.next.next;
    if (s.next ==null){break;}
    s.next = s.next.next;
}
if (t==null){t=heade;}
else if (t.next==null){t.next = heade;}

should be:

        if (t.next==null) {
            break;
        }
        t.next = t.next.next;
        if (s.next ==null) {
            break;
        }
        s.next = s.next.next;
    }
    if (t==null) {
        t=heade;
    } else if (t.next==null) {
        t.next = heade;
    }

and ...

static class Node
{
    int val; Node next;
    Node(int v){val=v;}
}

should be:

static class Node {
    int val;
    Node next;
    Node(int v) {
        val=v;
    }
}

Note that the community consensus for code style in Java is that {} braces should be opening at the end of the line, not the start of the next. I understand if your local work environment may have different "rules", but you should be aware that it is different to common Java style.

Your variable names are awkward. Things like "uneven" are not the opposite of "even" in this case, the opposite is "odd". Also, s and t are variables that I could not "imagine" what they are short for. If a 1-letter variable name is not special, it should at least make some sense... i is for index, use x and y in coordinate type variables, use p for position, or something.... but in your context t=headu, s=heade and I cannot think of something that s and t could mean.

Your main method, and the way it accepts the argument for the "size" of the test list, confused me a bit. I had to figure out the format of the input, etc. and how to make it run. You should comment things like that.

Now, about your algorithm.... it is not bad, it essentially builds two lists, and appends the one to the other, but I am concerned about the exit conditions of the loop... you have multiple of them (the for-loop conditions, and then multiple break conditions with "recovery" after the loop.

This is because you are tracking multiple pointers through the source list.

If you just iterate with one pointer in the source list, and have conditional code inside the loop, it's cleaner.

public static void strangerSort(Node list) {
    if (list == null || list.next == null) {
        // already stranger sorted.
        return;
    }

    Node eventail = list;
    Node oddhead = list.next;
    Node oddtail = oddhead;
    boolean even = false;
    // start from 3rd item in list
    // (guard condition guarantees at least 2 nodes)
    Node next = oddtail.next;
    while (next != null) {
        Node n = next;
        next = next.next;
        even = !even;
        if (even) {
            eventail.next = n;
            eventail = n;
        } else {
            oddtail.next = n;
            oddtail = n;
        }
    }
    eventail.next = oddhead;
    oddtail.next = null;
}

Answer 2

Naming

t, s, x, x2, headu, heade, N, v, val are all bad names.

There are very few situations where one (or two) character names are appropriate. Basically just i/j for a loop variable (but just where a better name doesn't make sense), x/y for coordinates, and well-known variable names in mathematical/physical equations (and even there I may prefer eg velocity to v).

In your situation, it is for example quite unclear how t and u and s and e relate to each other.

Better names for the strangeSort function variables may be related to what they actually do (so something with even and odd in the name).

Formatting

You should paste your code into any IDE and let it format it for you.

While you are mostly (although not completely) internally consistent, there are many oddities which make the code harder to read, including minor things such as odd spacing and multiple assignments on one line, and more important things such as missing newlines.

Unnecessary Code

if (t==null){t=heade;}

This isn't necessary, as you never use t.

Unnecessary Variables

headu is only used once, so you might as well remove it.

Comments

Normally, I complain as code contains too many comments which are unnecessary. In your case, I would have appreciated one or two comments.

For example, why is this at the end necessary?:

    if (t==null){t=heade;}
    else if (t.next==null){t.next = heade;}

It's obviously for some sort of corner-case, but which one?

Confusing for loop

The null check isn't the worst part about the loop. The worst part is that you change t and s on every iteration, and additionally modify t and s inside the loop as well, which is difficult to understand.

Now, the easiest solution would be to use two temporary lists (even and odd), iterate over the original list, put the values in the correct list, and then join the lists at the end. I'm assuming that you are not doing this for time and space reasons.

An alternative may be to use a while loop.

Unit Tests

I didn't write an alternative solution, as things like these are a lot easier to write when you have unit tests. You can make a small change, run the tests, and see if it breaks something. Without tests, making changes is rather difficult. You may want to consider writing unit tests first and then implementing against them in the future.