Reverse a Linked List

I’m surprised at how often this question pops up on interviews and undergraduate exams in imperative languages. While there are many ways to reverse a linked list, the most efficient technique by far is the use of iteration and some clever pointer manipulation. The trick is to always keep track of the previous, current, and next state of the system:

Node *reverse(Node *x) {
   Node *current = x;
   Node *previous = NULL;

   while (current != NULL) {
      Node *next = current->next;
      current->next = previous;

      /* switch to new node */
      previous = current;
      current = next;

   return previous;

In a non-destructive functional language like Scheme, we’re trick free and perform the standard recursive approach:

(define (my-reverse a-list)
  (if (null? a-list) '()
      (append (my-reverse (cdr a-list)) 
                      (list (car a-list)))))    

And just for kicks, we conclude with a deep reverse, which reverses both lists and sublists:

(define (deep-reverse a-list)
  (cond ((null? a-list) '())
        ((list? a-list) 
         (append (deep-reverse (cdr a-list)) 
                 (list (deep-reverse (car a-list)))))
         (else a-list)))    
Posted in Uncategorized