98. Segregate 0s, 1s, and 2s in a Linked List

A singly linked list contains only the values 0, 1, and 2. Rearrange it so every 0 comes before every 1, which comes before every 2, preserving the original relative order of nodes within each value group. Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, each 0, 1, or 2, the list's values in order. Output: Print the rearranged values, space-separated, on one line, with all 0s first, then all 1s, then all 2s.

1 <= n <= 10^5

Using 'dummy head' nodes for each of the three chains as you build them avoids awkward special-casing for each chain's very first node - a small, broadly useful technique for any 'build a chain while walking a list' problem.

Rearrange a linked list containing only 0s, 1s, and 2s so all 0s come first, then all 1s, then all 2s. Brute force: Copy all values into an array, sort the array with a general-purpose sort, and rebuild the list - this costs O(n log n), unnecessary when there are only 3 possible values to deal with. Optimised: Since there are only 3 possible values, building three separate chains directly out of the EXISTING nodes (rather than sorting) and concatenating them achieves the segregation in a single linear pass, with no comparisons between arbitrary values needed at all - just bucket classification, exactly like the array version's Dutch National Flag idea, adapted to linked-list relinking.

Maintain three separate dummy head/tail pointers, one each for a zero-list, a one-list, and a two-list. Traverse the original list exactly once, and for each node, unhook it and append it (by relinking pointers, not copying values) to the tail of whichever of the three lists matches its value; at the end, link the zero-list's tail to the one-list's head, the one-list's tail to the two-list's head, and terminate the two-list. This needs only a single traversal with no counting phase and no value-overwriting, working purely by rewiring the existing nodes, which also preserves each node's identity rather than just its value. Time: O(n) Space: O(1)

Make one pass through the list counting how many nodes hold 0, how many hold 1, and how many hold 2, then make a second pass overwriting the node values in order: first that many 0s, then that many 1s, then that many 2s. Because there are only three possible values, one counting pass followed by one overwrite pass is enough to produce the correctly segregated sequence, avoiding any sorting altogether and using only constant extra space beyond the three counters. Time: O(n) Space: O(1)

Traverse the linked list once to copy every node's value into an array, sort that array (or simply count how many 0s, 1s, and 2s there are), and then traverse the list a second time overwriting each node's value according to the sorted order. This is correct since only the final sequence of values matters, but treating it as a generic sort ignores the fact that there are only three possible values, and using a comparison sort wastes time better spent just counting. Time: O(n log n) Space: O(n)

1. Build THREE separate small chains as you walk the list once: one collecting 0s, one collecting 1s, one collecting 2s, each in the order encountered. 2. Concatenate the three chains together at the end: 0s chain, then 1s chain, then 2s chain.

Time: O(n) - one single pass through the list. Space: O(1) extra space - relinking existing nodes into three chains, no new allocation.

n = 1 (a single node, unchanged); a list containing only one of the three values (one group empty); n = 10^5 for performance.

Be ready to connect this directly to the array version ('Sort an Array of 0s, 1s and 2s') - the underlying idea (three buckets, no general sorting needed) is identical, just adapted from array partitioning to linked-list chain-building.