Explain the recursive method to reverse a singly linked list and the base/recursive steps.

• A. Sort the list first then reverse.
• B. Base: head is NULL or head.next is NULL; return head. Recursive: reverse head.next to get rest; then set head.next.next = head; set head.next = NULL; return rest.
• C. Base: head is non-empty; swap values.
• D. Base: use a loop to reverse pointers without recursion.

Answer: (C)

The idea being tested is reversing a singly linked list by changing the links through recursion, not just moving values. The correct approach uses a base case that detects when you’ve reached the end (or an empty list) and then rewires pointers on the way back up the call stack.

Base case: if the list is empty or has a single node, you can return that node as the new head, since nothing else needs to be done.

Recursive step: reverse the rest of the list starting at the next node (let rest = reverse(head.next)). After this call, rest is the head of the already-reversed portion. To put the current node at the end of that reversed portion, set head.next.next = head. This links the next node back to the current node, effectively putting head after the reversed tail. Then detach the current node from the rest by setting head.next = NULL. Finally, return rest as the new head of the reversed list.

For example, turning 1->2->3 into 3->2->1 works by first reversing 2->3 to 3->2, then linking 1 after 2 and setting 1’s next to NULL, yielding 3->2->1.

Swapping values, while it may appear to “reverse” the sequence of data, does not rearrange the actual node links, so it isn’t the same recursive pointer reversal. A loop-based approach is iterative, not recursive.