Reverse a single linked list

Given a singly linked list, how do we reverse it by re-arranging the links?

For example if the given linked list is 1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL.

The following diagram shows the simple steps to perform the reversal.

And here is the C++ code which includes both recursive and iterative versions of reversal method.

	#include <iostream>

	using namespace std;

	struct Node
	{
	int data;
	Node * next;
	};

	void Print(Node * head)
	{
	while ( head )
	{
	cout<< head->data << " ";
	head = head->next;
	}
	cout << endl;
	}

	Node * Insert(Node * head, int d )
	{
	Node * newNode = new Node();
	newNode->data = d;
	newNode->next = head;
	return newNode;
	}

	//Iterative version of reversing a single linked list
	Node * Reverse(Node * head)
	{
	if( head == NULL \|\| head->next == NULL )
	return head;

	Node * prevNode = NULL;
	Node * curNode = head;

	while( curNode != NULL )
	{
	Node * nextNode = curNode->next;
	curNode -> next = prevNode;
	prevNode = curNode;
	curNode = nextNode;
	}

	return prevNode;
	}
	//Recursive version of reversing a single linked list
	Node * RecursiveReverse(Node * head)
	{
	if( head == NULL \|\| head->next == NULL )
	return head;
	Node * first = head;
	Node * rest = head->next;
	rest = RecursiveReverse(rest);
	first->next->next = first;
	first->next = NULL;
	return rest;
	}
	int main()
	{
	Node * head = NULL;
	head = Insert(head, 1);
	head = Insert(head, 2);
	head = Insert(head, 3);
	head = Insert(head, 4);
	head = Insert(head, 5);
	Print(head);

	head = RecursiveReverse(head);
	Print(head);

	head = Reverse(head);
	Print(head);

	return 0;
	}

by GitHub