Reverse Linked List Recursively without using any new variable

Question

In a job interview I was asked to write a function in C that recursively reverses a linked list, returns the new first node, and doesn't use any new nodes.

How can you do this?

Answer 1

Here's the general idea, in an agnostic language with C-like syntax:

Node invert(Node list, Node acc) {
    if (list == null)
        return acc;
    Node next = list.next;
    list.next = acc;
    return invert(next, list);
}

The above function receives the first node of the list to be inverted and the accumulated value so far, and returns the head of the newly-inverted list - the reversal of nodes is done in-place, no extra space is allocated (besides a local variable in the stack). Call it like this:

invert(firstNodeOfList, null);

This is an example of a tail recursion: the result gets collected in the acc parameter, and when each recursive call returns, there's nothing left to do, just return the accumulated value.

UPDATE:

In a functional language it's easier and more natural to write a function to reverse a list without using a local variable, for instance look at the following code in Scheme - it has drawback, that it will create a new list node when calling the cons procedure:

(define (invert lst acc)
  (if (empty? lst)
      acc
      (invert (rest lst)
              (cons (first lst) acc))))

(invert '(1 2 3 4 5) '())
> '(5 4 3 2 1)

Bottom line: you either create a new node or create a new local variable at each recursive call, but unless the programming language offers an expression for sequential execution and the compiler guarantees evaluation order (see @WillNess' answer) you can't eliminate both and have a working algorithm. Better play it safe and use a temporary variable for enforcing evaluation order and always obtaining correct results.

Answer 2

This is very simple: recurse to the end of the list, passing in the new next pointer each time and returning the end of the list.

struct list {
    struct list *next;
};

struct list *reverse(struct list *cur, struct list *prev) {
    struct list *next = cur->next;
    cur->next = prev;
    if(next == NULL) return cur;
    return reverse(next, cur);
}

reverse(head, NULL);