数据结构 - 反转单链表的递归算法（C++）

#include <iostream>

#define NULL 0

using namespace std;

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

Node* create()
{
	Node* head = NULL;
	Node* rear = head;
	Node* p; // The pointer points to the new created node.
	char  tmp;

	do
	{
		cout << "Please input integer or char '#':";
		cin >> tmp;
		if(tmp != '#')
		{
			p = new Node;
			p->data = tmp;
			p->next = NULL;

			if(head == NULL)
			{
				head = p;
			}
			else
			{
				rear->next = p;
			}
			rear = p;
		}
	}
	while(tmp != '#');

	return head;
}

void print(Node* head)
{
	cout << "The current list is: ";
	Node* p = head;
	if(head != NULL)
	{
		do
		{
			cout << p->data << cout << ' ';
			p = p->next;
		}
		while(p != NULL);
	}
	cout << "\r\n";
}

Node* reverseSingleLinkedListRecursive(Node* p, Node*& head)
{
	if(p == NULL || p->next == NULL)
	{
		head = p;
		return p;
	}

	Node* tmp = reverseSingleLinkedListRecursive(p->next, head);
	tmp->next = p;
	p->next = NULL; // To prevent forming a ring.
	return p;
}

int main()
{
	Node* list = create();
	print(list);
	reverseSingleLinkedListRecursive(list, list);
	print(list);

	return 0;
}

// Output:
/*
Please input integer or char '#':1
Please input integer or char '#':2
Please input integer or char '#':4
Please input integer or char '#':6
Please input integer or char '#':3
Please input integer or char '#':8
Please input integer or char '#':7
Please input integer or char '#':9
Please input integer or char '#':0
Please input integer or char '#':#
The current list is: 10F69C3E8 20F69C3E8 40F69C3E8 60F69C3E8 30F69C3E8 80F69C3E8 70F69C3E8 90F69C3E8 00F69C3E8
The current list is: 00F69C3E8 90F69C3E8 70F69C3E8 80F69C3E8 30F69C3E8 60F69C3E8 40F69C3E8 20F69C3E8 10F69C3E8
*/