A line of text is stored as a singly linked list with one character per node. A word is a
maximal run of non-space nodes and a gap is a maximal run of space nodes (" "). The line may
start or end with a gap.
Rearrange the nodes so that the words appear in reverse order while every gap stays exactly
where it was: the pattern of gap lengths (including a leading or trailing gap) is unchanged, and
the letters inside each word keep their own order. Return the new head (None for an empty
line). Re-link the existing nodes; do not create new ones.
The tests show the chain as a string, "".join(linked_to_list(...)).
Examples
Input: "go far away"
Output: "away far go"
Input: " a bc d "
Output: " d bc a "
Input: " "
Output: " "
Constraints
0 <= number of nodes <= 6 * 10**4- Every node holds one character: a space or a printable non-space character.
- Target: O(n) time. Walking from the head to find each next word is too slow for the large tests.
Goals
- Cut a chain into maximal segments without losing any node
- Use a stack for pieces that come back reversed and a queue for pieces that keep their order
- Re-stitch segments with O(1) work each