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

迷南。 2022-06-15 07:21 149阅读 0赞

链表的学习是我们在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;
    }

运行的结果如下：

![Center][]

[Center]: /images/20220615/47f76c126ca5410cb9fd2184949bfe07.png