Programming Problem: Reverse Singly-Linked List Using Recursion

This is one of the series of articles on programming problems. Usually these problems are small and interesting and some arise from simplification of larger problems to make the solution easier to understand and implement.

The problem we are going to solve in this article is to reverse a singly-linked list (SSL) using recursion. For example, given a SLL like the following:

 head
  |
  1 -> 2 -> 3 -> 4

it should become the following after reversal:

                head
                 |
  1 <- 2 <- 3 <- 4

It is easy to implement the reversal iteratively. However, as an exercise we want to solve it with recursion.

We can think of recursion as solving a problem of size N given that we have already solved the problem of size N-1. Usually it is trivial to solve problem of size 0 or 1 which serves as the base for recursion. In this case, N is the number of nodes in the SLL. The key part is to identify how we break the size-N problem into smaller problems such that we can solve it when we have the solution for the problem of size N-1.

Now suppose we have done the reversion of all but the last node as follows:

            head
            |
----------------
| a <- b <- c  |  d
----------------

Here the N-1 problem is to reverse the first N-1 nodes of the SLL. Then we need to update d's pointer to point to the head of the N-1 list and then update the head to point to d.

The problem is that how we can get to the subproblem of reversing a to c first or how we we can break the list from node d, the last node in the list.

If we have to traverse the list to get to d, then we probably shouldn't use recursion at all because this basically becomes an iterative process. Even if we maintain a tail pointer to d, there is still no way for us to get to its previous node c from d. So this way of recursion doesn't work.

Now let's try it another way. Suppose we have reversed the list from b to d.

              head
               |
  ----------------
a | b <- c <-  d |
  ----------------

If we have a tail pointer that points to b, the last node in the newly reversed sub-list, then we just need to update b's next pointer to point to a and move the tail pointer to a. So this way of recursion is feasible and we just need to maintain a head pointer and a tail pointer in our list data structure. The tail pointer is also useful when we need to insert a node to the end of a list because it is then an O(1) operation. Otherwise we have to iterate through the list to the end and it becomes an O(N) operation.

For illustration purpose, we can define a list_head struct and a node struct.

typedef struct list_head {
	struct node* head;
	struct node* tail;
} list_head;

typedef struct node {
	struct node* next;
	int value;
} node;

We also define a simple function to initialize a 4-node linked list.

#define NODES 4

node n[NODES];

list_head init_list()
{
	int i;
	list_head h;
	for (i=0; i<NODES-1; ++i) {
		n[i].next = &n[i+1];
		n[i].value = i+1;
	}
	n[NODES-1].next = 0;
	n[NODES-1].value = NODES;
	h.head = &n[0];
	h.tail = &n[NODES-1];
	return h;
}

We use global variables because memory management is not our concern here.

We can also define a helper function to print the linked list in order.

void print_list(list_head h)
{
	node* p = h.head;
	while (p)  {
		printf("%d ", p->value);
		p = p->next;
	} 
	printf("\n");
}

Now we are ready to write the reverse function with recursion. Its prototype is list_head reverse_list(list_head h).

The base case is very simple: If the linked list is empty or just contains one node, then we don't need to do anything and we can just return the original list head.

	if ((h.head == 0) || (h.head->next ==0)) {
		return h;
	}

Otherwise, we first create the sublist and return its head in nh:

	list_head nh;
	nh.head = h.head->next;
	nh.tail = h.tail;

The list pointed to by nh is just the original list sans the first node. Then we can call the reverse function for the sublist and store the new list head back to the same variable nh:

	nh = reverse_list(nh);

Now we just need to terminate the first node's next pointer with 0, and have nh's tail node's next pointer and the tail node pointer itself point to the first node and then return nh:

	h.head->next = 0;
	nh.tail->next = h.head;
	nh.tail = h.head;
	return nh;

You can download the complete C program that reverses a singly-linked list using recursion and study it yourself.

Back to articles on development