How to Reverse a Singly Linked List Recursively

Bahadir Balban

Started Tech Buzz

@learningalgorithms

I came across this problem while searching for interview questions.

Before you look at the code, here are the key points with this solution.

Recursion

Recursion is all about solving a problem in smaller chunks at a time, until you hit the special case condition.

E.g. given a list, and asked for a transformation on that list, call a recursive function that transforms the 1 element smaller version of that list, and return the result (in our case, this is a reversal)

In the special case that there is no more smaller version of the data set left, return the result, which is the smallest possible partial result to the problem. (in the case of reversal, simply return the last element)

The part I spent more time on this problem is that each time you get a reversed list, you need to append the current element to the _end_ of the list, however, you need to return the head. So you need to traverse to the end of the reversed list you get, each time to add the current element, then return the HEAD.

This does increase the runtime complexity, nevertheless it is a working recursive solution.

The complexity of this problem is close to O(n) * O(n). n for traversal of the entire list by recursion, and (n-1) at each level of recursion to get to the tail of the reversed list.

A nice part is that the code for this solution looks simpler than most C++ answers on the web.

Here is how it works (written in C):

#include <stdio.h>
struct list {
	int val;
	struct list *next;
};
#define LSIZE 5
struct list lmem[LSIZE] = { 0 };
void print_list(struct list *l) {
	while (l != 0) {
		printf("%d ", l->val);
		l = l->next;
	}
	printf("%s", "\n");
}
void init_list(struct list *l)
{
	for (int i = 0; i < LSIZE; i++) {
		l[i].val = i;
		l[i].next = &l[i+1];
		if (i == LSIZE - 1) {
			l[i].next = 0;
		}
	}
}
struct list *gettail(struct list *l) {
	while(l->next)
		l = l->next;
	return l;
}
struct list *reverse_list(struct list *cur)
{
	struct list *rev, *tail;
	print_list(cur);
	// Special case: If no more elements left, 
	// return current one.
	// It satisfies the smallest solution to the problem.
	// The reverse order of
	// a single linked list element is also the same.
	if (!cur->next) {
		return cur;
	}
	// Reducing problem: the recursive call gets a 
	// 1 element smaller list to reverse
	// We expect 'rev' represents the HEAD of the 
	// reversed, smaller list returned to us
	// from the deeper levels of recursive calls.
	rev = reverse_list(cur->next);
	// Get to the tail of the reversed list
	tail = gettail(rev);
	// Add current element as the next one
	tail->next = cur;
	// Here is a part I made a mistake the first
	// time, zero-terminate
	// the list you are returning.
	// This ensures the final return, will have 
	// null terminated list.
	cur->next = 0;
	return rev;
}
int main(int argc, char *argv[])
{
	struct list *rev;
	init_list(lmem);
	print_list(lmem);
	rev = reverse_list(&lmem[0]);
	print_list(rev);
	return 0;
}




Join The Discussion