99. Segregate Even and Odd Nodes in a Linked List

A singly linked list contains n integer values. Rearrange it so all even-valued nodes come before all odd-valued nodes, preserving the original relative order within each group. Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print the rearranged values, space-separated, on one line - all evens first (original relative order), then all odds.

1 <= n <= 10^5

Preserving each group's ORIGINAL RELATIVE ORDER (not just separating them arbitrarily) is the key requirement here - building two chains IN THE ORDER ENCOUNTERED naturally guarantees this, with no extra sorting needed.

Rearrange a linked list so all even-valued nodes come before all odd-valued nodes, keeping each group's original relative order. Brute force: Copy all values into an array, partition the array into evens and odds (preserving relative order within each), and rebuild the list from the partitioned array - this works but discards the existing nodes unnecessarily. Optimised: Building two separate chains DIRECTLY out of the EXISTING nodes (rather than copying values) as you walk the list once, then simply linking one chain after the other, achieves the segregation with no extra allocation - just careful pointer bookkeeping for two running tails.

Traverse the list once collecting even values into one array and odd values into another (preserving encounter order within each), then build an entirely new linked list by allocating fresh nodes for the even values followed by fresh nodes for the odd values, discarding the original list. This is correct and simple, but it uses extra memory proportional to the whole list twice over - the temporary arrays plus a brand-new set of nodes - none of which is necessary since the original nodes could be reused directly. Time: O(n) Space: O(n)

Traverse the list once, and for each value, immediately append a new node to either an 'evens' chain or an 'odds' chain being built as you go, then join the two chains at the end. This avoids the brute approach's two separate array-collection passes, doing everything in one traversal, but it still allocates n new nodes rather than reusing the ones already in the original list. Time: O(n) Space: O(n)

Traverse the original list once, and instead of allocating anything new, redirect the existing nodes' next pointers to build two chains in place - an even chain and an odd chain, each tracked with a head and tail pointer - then, once the traversal ends, point the even chain's tail at the odd chain's head (and null-terminate the odd chain's tail). Because every node is reused exactly where it already lives in memory, this needs no extra node allocation or arrays at all beyond a handful of pointers, making it both time- and space-optimal. Time: O(n) Space: O(1)

1. Walk the list once, building TWO separate chains as you go: one collecting even-valued nodes, one collecting odd-valued nodes, each in the order encountered. 2. Once the walk is done, attach the ODD chain right after the EVEN chain's last node.

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

n = 1 (a single node, unchanged); a list that is entirely even or entirely odd, leaving one group empty; n = 10^5 for performance.

Be ready to use 'dummy head' nodes for both the even and odd chains as you build them - this small technique avoids awkward special-casing for each chain's very first node.