Sorting the dummy-head list, line by line

The two routes

Every node owns two fields: data, the value it carries, and next, the reference to the node after it. A sort must end with the values in ascending order when you read the chain, and there are exactly two ways to get there.

Vocabulary, glossed: people say sort the data for the first route and sort in place by relinking for the second. An exam variant can ask for either, so read the starter file before deciding: the field types, the given methods, and the file comment tell you which shape the graders expect. Arrays are a third setting with their own drills: Selection Sort and Insertion Sort sort an array in place by swapping cells.

The dummy head

The constructor builds one node before any element arrives: head = new Node(null, null). That node is a sentinel (a placeholder that marks the front). It exists so every real node has a predecessor, which makes insertion and removal code uniform. The price: its data is null, and null.compareTo(anything) throws NullPointerException. So every traversal in sort() starts at this.head.next, the first real node. Starting at head fails all nine tests at once, because each test converts any exception into a failure.

Reading what a test built

The tests build their lists with addFirst, which lands each element directly behind the dummy. Each call pushes the previous elements back one place, so the reading order is the reverse of the call order:

Check the call order before predicting any expected string. Three other exam tasks need the same read.

The traversal shape

Start at the first real node, stop on null, advance one node per step. On the empty list, head.next is already null, so the body runs zero times: no guard, no crash. That is why testSortListEmpty passes on loop shape alone. Test every list method in your head at three sizes: zero, one, many.

The min scan: a reference on the move

Finding the smallest element is its own move, separate from putting it anywhere. min is a node reference, a name with an arrow to one node, and the scan re-points that arrow whenever it meets strictly smaller data:

The comparison goes through compareTo because the data field is declared as the Comparable interface: negative means smaller, zero means equal, positive means larger. For the fruit strings in the tests, that is dictionary order. This is how most people sort a hand of cards: scan for the lowest, put it first, repeat on the rest.

The size guard

Lists of size 0 and 1 are sorted by definition, so the reference returns before any loop. The guard is required for the empty list: there start = this.head.next is null, and the loop test start.next != null throws NullPointerException, so testSortListEmpty fails. Size 1 is the only size the loop bound covers on its own. Write the guard every time.

The three-line trade

Two values cannot pass through one variable at the same time, so temp holds the first while the second crosses, then temp lands in the freed slot. temp is declared Comparable because that is the data field’s declared type. When min and start are the same node, the trade copies a value onto itself, which is harmless: the already-sorted tests pass with no special case.

What the data trade never changes

The trade writes data fields only, so after any number of passes: size is unchanged, head is unchanged, and every next field is unchanged. This matters because every one of the nine expected strings opens with List size is: N. Touch size inside sort() and all nine tests fail at their first asserted line.

One pass, one settled position

Scan the whole list for its minimum, trade it into the front node: position one is now final for any input. That single move, repeated from one position later each pass, is the sort. This is why selection sort is the lowest-risk hand-written sort here: the move is small, visual, and identical every pass.

The outer loop and its bound

Each pass scans from start.next and trades with start. The bound is start.next != null because a one-node remainder is already sorted: the last node needs no pass. The same bound makes size 1 run zero passes; size 0 never reaches it, because the guard returns first. start != null also sorts correctly; it just spends one extra pass scanning an empty tail. The tests use at most 10 nodes, so the n squared pass count is fine.

Pass by pass

After pass k, the first k positions hold the k smallest values in final order, and everything behind them has changed by at most one trade per pass. A list of n nodes finishes in n minus 1 passes; the last node inherits its place. Tracing a scrambled four-list through its three passes, by hand, is the fastest way to make the loop bounds feel inevitable instead of memorized.

Direction is one character

compareTo(min.data) < 0 finds the minimum and sorts ascending. Flip it to > 0 and every pass pulls the largest value forward instead: descending output, and all nine exact-string tests fail on their first value line. The two already-sorted tests exist precisely to catch this: a correct sort must leave sorted input untouched.

The frozen walker

A hand-rolled while (cur != null) that forgets cur = cur.next compares the same node forever: the condition never changes, the run never finishes, and code that runs forever scores 0 for the problem. The for form carries the advance in its header, which is a real argument for preferring it when tired.

Duplicates and strict <

Equal values compare to 0, and 0 < 0 is false, so min never moves onto an equal value: the first-met smallest wins each pass. Nothing is ever merged or dropped, because trading data cannot remove a node. The heaviest test feeds five values twice each and expects all ten back, adjacent: apple apple grape grape lemon lemon lime lime orange orange under List size is: 10. Strict < is the reference, but it is not why the test passes: <= passes it too, because any correct sort puts equal values side by side. Nor does strict < keep equal values in their first order: the trade can carry one past its twin, so 2a 2b 1 sorts to 1 2b 2a. A relinking mistake is what this test punishes: a lost node prints nine lines under a size line that still says ten.

The fences, and the rename that costs everything

You write only between //startMethod and //endMethod, in only the file the problem names. One rename breaks the whole module: change the class header while the constructor keeps the old name, and javac answers invalid method declaration; return type required, because a constructor whose name no longer matches the class reads as a method with no return type. A file that does not compile is 0 for the module. The distributed V2 reference snapshot ships with exactly this failure: even the reference scores zero when a name changes.

The nine tests and the CRLF fact

Every assertion is assertEquals on list.toString(), compared character for character. The given toString ends every line with \r\n, including the last: you never type those bytes, you only leave toString untouched. The nine scenarios: empty, one item, two items, two sorted, three items, three sorted, ten fruits sorted, the same ten scrambled, and ten with five duplicated values. Self-check on exam day against the Main file’s trailing comment block, line by line, before the hidden tests ever run.

• Start every traversal at this.head.next. The dummy’s data is null.
• Strict < in the compare. Flipping it fails all nine tests.
• Trade data with a Comparable temp; write no next field on this route.
• Never touch size, head, toString, addFirst, or any name.
• No Arrays.sort, Collections.sort, List.sort, or Stream.sorted: a person reads sort() and writes 0.
• Loops and recursion are both legal here; the no-loops rule belongs to Recursion.
• Before submitting: search sort() for ".sort(", then run the Main and diff its comment.