Reversing an immutable linked list cannot rearrange its existing links: the original list must remain unchanged. Instead, walk the list and build a new one. Each item is pushed onto the front of the result, so the last item visited ends up first. section 1.2.2
public LinkedList<T> Reverse()
{
var result = Empty;
for (var list = this; !list.IsEmpty; list = list.Tail!)
result = result.Push(list.Value!);
return result;
}
The result starts empty. The loop visits each item once and uses Push to prepend it to a new list; it never changes the input. section 1.2.2
Order without mutation
Starting with 50 40 30 20 10, Reverse produces 10 20 30 40 50. Both lists can be printed afterward because the original is unchanged. Reversal takes O(n) time and O(n) extra memory. section 1.2.2
The same operation solves a less obvious problem in an immutable queue built from two stacks. Normally, Dequeue pops the dequeue stack. When that pop empties it but the enqueue stack still has items, reversing the enqueue stack makes it the new dequeue stack. That transfer restores the order needed for subsequent dequeues; the ordinary case remains an O(1) pop. section 2.4
