In this post i will present to you 3 ways on how to reverse a linked list. Using full implementation with 3 pointers and another with recursion, and finally one sketch of solution that harnesses the STL(Standard Template Library)

What is a Linked List?

A “Linked List” is a data structure that contains data in a certain order, whereas each quanta of data is being stored in a node and each node points at the next node(since order matters here..).

Reversing a List

The meaning here is to reverse the order between the nodes. Sometimes we change the data itself, but it is proffered to change the pointers  rather than the data.

suppose we have this list:
(1)->(2)->(3)
after reversing the list, we should end up with this list:
(3)->(2)->(1)
Notice that we don’t need to allocate a new memory for the reversed list..

Before we start off, let’s start by a few type-defs and bases:

/*
 * reverseLinkedList.c
 *  Created on: 19 February 2015
 *      Author: bassam
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node_t* Node;

struct node_t {
	int data;
	Node next;
};

3 pointers:

void reverseList(Node* head) {
	Node next = NULL;
	Node pre = NULL;
	Node curr = *head;
	while (curr != NULL) {
		next = curr->next;
		curr->next = pre;
		pre = curr;
		curr = next;
	}
	*head = pre;
}

This solution is neat, simple and easy to trace and debug..

Recursion:

This approach is a little bit harder than the one before, take few minutes to grasp the idea behind each call in the recursion, think what would happen when reaching a list with one node and how the backtracking is performed, by attention that when returning from a recursion call to the previous one, look at the code from the point of the recursion call not from the start!

/* reference to this code(from geeksforgeeks.org):
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf */

void RecursiveReverse(Node* headRef) {
	Node first;
	Node rest;
	if (*headRef == NULL)
		return; // empty list base case
	first = *headRef; // suppose first = {1, 2, 3}
	rest = first->next; // rest = {2, 3}
	if (rest == NULL)
		return; // empty rest base case
	RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
							 // after: rest = {3, 2}
	first->next->next = first; // put the first elem on the end of the list
	first->next = NULL; // (tricky step -- make a drawing)
	*headRef = rest; // fix the head pointer
}

C++ STL – idea sketch:

No implementation for this part at this moment. But the idea is by using the std::Stack() and std::vector() templates:

Since the Stack is FILO(First In Last Out), we can insert the nodes of the list into a stack, and then to pop them out one by one and push them to a vector. Thus we get a vector with the nodes at a reversed order

Testing:

Copy this code along with the code above to a new project

void printList(Node list) {
	Node curr = list;
	while (curr != NULL) {
		printf("%d\n", curr->data);
		curr = curr->next;
	}
}

/*******************************************************************/
int main() {
	Node list = malloc(sizeof(*list));
	list->data = 0;
	list->next = malloc(sizeof(*list));
	list->next->data = 1;
	list->next->next = NULL;
	printf("List in original order:\n");
	printList(list);

	printf("testing 3 pointer solution:\n");
	reverseList(&list);
	printf("**************************\n");
	printList(list);
	reverseList(&list);//reverse again to restore original order

	printf("testing 3 recursive solution:\n");
	RecursiveReverse(&list);
	printf("**************************\n");
	printList(list);
	return 0;
}

The output you’ll get is similar to this:

solving
i used eclipse Kepler on windows to run and compile this
Advertisements