Which head goes first

Heads are chosen going down. Links are written coming back up.

Switch the comparison between <= and < and watch which list wins a tie. The values stay identical; the origins do not.

compare
list1
list2
merged
from list1 from list2 current head link not written yet

 

Press Next to make the first call.

Call stack

    func

    Two halves of one call

    Watch the merged row fill left to right during the descent, with every link dashed. Each frame picks the smaller head and passes the rest along, but it cannot finish, because it does not yet know what follows. Then the base case returns the leftover list whole, and the links solidify right to left on the way back up.

    The order of the answer is decided going down. The answer itself is assembled coming back up.

    That is the difference from LC 206, where nothing at all happens on the way down. Same leap of faith, opposite half of the call.

    What <= is protecting

    Load ties everywhere and flip the comparison. The merged values are identical either way, [1,1,1,1,2] both times, but the colours change: with <= the list1 cells come first on every tie, with < the list2 cells do.

    That is stability. LC 21 cannot detect it, since equal values are interchangeable here. Inside merge sort, where each element carries other fields, it is the whole difference between a stable sort and an unstable one.

    Why no remainder loop

    When one list empties, the base case returns the other one as it stands: already sorted, already linked. The iterative version has to walk and append that tail by hand. Here it is one return. Load one runs out early: list2 empties first, and the whole of [5] arrives in a single step.