【面试题】剑指offer05--逆序打印链表

链表的学习是我们在C++里面重要的一个知识点，在链表的学习中，我们使用的是结构体的定义，我们要实现的是链表的初始化和链表的节点的插入，打印的时候有正序的打印和逆序的打印，接下我们来学习一下关于链表的逆序打印。

首先创建一个结构体，定义链表里面的数值和下一个节点：

struct ListNode//定义一个链表的结构体
{
	int _data;
	ListNode* _pNext;
};

接下来初始化链表，创建一个新的节点：

void InitList(ListNode** phead)//初始化链表为空
{
	*phead = NULL;
}

ListNode* BuyNewNode(int data)//创建一个新的节点
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = data;
	newNode->_pNext = NULL;
	return newNode;
}

尾插一个节点：

void PushBack(ListNode** phead, int data)
{
	assert(phead);
	ListNode* newNode = BuyNewNode(data);
	if (*phead == NULL)
	{
		*phead = newNode;
		return;
	}

	ListNode* cur = *phead;
	while (cur->_pNext)//如果cur的next不为空的时候
	{
		cur = cur->_pNext;
	}
	cur->_pNext = newNode;
}

在逆序的时候，可以选择递归方法和非递归的方法：

递归法：只要phead不为空，一直到最后一个节点，然后再递归回来：

void ReversePrintList(ListNode* phead)
{
	if (phead == NULL)
	{
		return;
	}
	ReversePrintList(phead->_pNext);
	cout << phead->_data << " ";
}

非递归法：在不创建新的链表得时候，我们使用了栈，因为栈是后进先出的，所以在插入节点的时候

我们最后一个节点最先pop出来，因此可以实现将链表逆置起来：

void ReversePrintListNonR(ListNode* phead)
{
	assert(phead);
	stack<ListNode*>s;
	ListNode* cur = phead;
	while (cur)
	{
		s.push(cur);
		cur = cur->_pNext;
	}
	while (!s.empty())
	{
		cout << s.top()->_data << " ";
		s.pop();
	}
	cout << endl;
}

以下是完整的代码：

#include<iostream>
using namespace std;
#include<assert.h>
#include<stack>

struct ListNode//定义一个链表的结构体
{
	int _data;
	ListNode* _pNext;
};

void InitList(ListNode** phead)//初始化链表为空
{
	*phead = NULL;
}

ListNode* BuyNewNode(int data)//创建一个新的节点
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = data;
	newNode->_pNext = NULL;
	return newNode;
}

void PushBack(ListNode** phead, int data)
{
	assert(phead);
	ListNode* newNode = BuyNewNode(data);
	if (*phead == NULL)
	{
		*phead = newNode;
		return;
	}

	ListNode* cur = *phead;
	while (cur->_pNext)//如果cur的next不为空的时候
	{
		cur = cur->_pNext;
	}
	cur->_pNext = newNode;
}

void PrintList(ListNode* phead)//正序打印链表
{
	assert(phead);
	ListNode* cur = phead;
	while (cur)
	{
		cout << cur->_data << " ";
		cur = cur->_pNext;
	}
	cout << endl;
}
void ReversePrintList(ListNode* phead)
{
	if (phead == NULL)
	{
		return;
	}
	ReversePrintList(phead->_pNext);
	cout << phead->_data << " ";
}
void ReversePrintListNonR(ListNode* phead)
{
	assert(phead);
	stack<ListNode*>s;
	ListNode* cur = phead;
	while (cur)
	{
		s.push(cur);
		cur = cur->_pNext;
	}
	while (!s.empty())
	{
		cout << s.top()->_data << " ";
		s.pop();
	}
	cout << endl;
}
int main()
{
	ListNode* phead;
	InitList(&phead);
	PushBack(&phead, 1);
	PushBack(&phead, 2);
	PushBack(&phead, 3);
	PushBack(&phead, 4);
	cout << "正序打印链表：";
	PrintList(phead);
	cout << "逆序递归发打印链表：";
	ReversePrintList(phead);
	cout << endl;
	cout << "逆序非递归法打印链表：";
	ReversePrintListNonR(phead);
	system("pause");
	return 0;
}

运行的结果如下：