Singly Linked List "Strange sorting" exercise

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 ");
}

/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;}

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;
}

StackExchange Code Review Q#157222, answer score: 6