Algorithm : Reverse singly linked list

Questions about singly linked list are the lovers of interviewers during interviews given the characteristic that singly linked list is one-directional list and it's difficult to get the previous node of one node without some buffering tricks. 

In this post, we will demonstrate one of the most frequently asked question about singly linked list -- Reversing the singly list.

Given the first node of a singly linked list, reverse the singly linked list. For example :

A->B->C->D

After reverse, it becomes:

D->C->B->A

The general idea here is to changing the next node of one to its previous node to realize reverse. The most difficult part to resolve this problem is able to find the next node of the one node after changing its next node to its previous node. To achieve this, a buffering to the node's next node is needed before changing its next node to its previous node.

Below is the sample code to this issue.

#include <stdio.h>

struct Node {
	struct Node* next;
	char value;
};

// Print the singlely linked list
void printList(struct Node* head){
	while (head != 0){
		printf("%c->", head->value);
		head = head->next;
	}
	printf("null\n");
}

// Reverse the singly linked list
struct Node* reverseList(struct Node* node){
	struct Node* currentNode = 0;

	while (node){
		struct Node* next = node->next;
		node->next = currentNode;
		currentNode = node;
		node = next;
	}

	return currentNode;
}

int main(){
	struct Node* a = malloc(sizeof(struct Node));
	struct Node* b = malloc(sizeof(struct Node));
	struct Node* c = malloc(sizeof(struct Node));
	struct Node* d = malloc(sizeof(struct Node));

	a->value = 'A';
	b->value = 'B';
	c->value = 'C';
	d->value = 'D';

	a->next = b;
	b->next = c;
	c->next = d;
	d->next = 0;

	// print the original list
	printList(a);

	// Reverse list
	struct Node* head = reverseList(a);

	// print the new list
	printList(head);

	free(a);
	free(b);
	free(c);
	free(d);
}

The output of this program is :

A->B->C->D->null
D->C->B->A->null

You may also be interested to Algorithm : Delete middle node from singly linked list.