Which method guarantees a new reversed list without mutating the original by constructing new nodes during traversal?

• A. Use a queue to hold data then rebuild.
• B. Reverse using in-place mutation.
• C. Create new nodes during traversal and prepend to a new list.
• D. Swap values in the original nodes.

Answer: (C)

The idea being tested is making a completely separate reversed copy by building new nodes as you walk the original list, so the original stays unchanged.

As you traverse the original list, you create a new node for each element and prepend it to the head of a new list. Because each new node is added to the front, the first value you see in the original ends up at the tail of the new list, and each next value becomes the new head, producing a reversed sequence. This guarantees a new reversed list without mutating the original since every node in the new list is freshly allocated.

This approach runs in linear time, since you visit each node once, and uses linear extra space equal to the number of nodes (one new node per original node). The other options either mutate the original (in-place reversal or swapping values) or don’t inherently ensure new nodes are created during traversal to form a separate reversed copy (a queue approach might read values but doesn’t by itself guarantee the construction of new nodes during traversal).