《剑指Offer》面试题6

 

1 问题

题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

 

 

2 分析

方式一：可先将链表的节点和指针进行反转，不过这样操作也改变了链表结构。

方式二：通过栈后入先出的规律，将节点通过栈结构，进行打印。

方式三：通过构造递归函数，实现链表的逆向打印。

 

 

3 代码

#include "iostream"
#include "stack"

using namespace std;

typedef struct node
{
	int m_nValue;
	node* m_pNext;
}ListNode;

//功能：通过栈结构将链表逆向打印
//输入：pHead 头节点地址
//输出：无
void PrintListReversingly_Iteratively(ListNode* pHead)
{
	std:stack<ListNode*> nodes;	//通过stack容器定义栈结构 nodes

	ListNode* pNode = pHead;
	while (pNode != nullptr)
	{//1.顺序遍历链表节点，将节点压如栈中
		nodes.push(pNode);		//将pNode压入栈中
		pNode = pNode->m_pNext;
	}

	while (!nodes.empty())
	{//2.依次从栈中取出元素，并打印节点的值
		pNode = nodes.top();			//从栈中弹出一个元素
		cout << pNode->m_nValue << ",";
		nodes.pop();					//移除栈顶元素
	}
	cout << endl;
}

//功能：通过递归的思想将链表节点逆序输出
//输入：pHead 头节点地址
//返回：无
void PrintListReversingly_Recursively(ListNode* pHead)
{
	if (pHead != nullptr)
	{
		if (pHead->m_pNext != nullptr)	//回归条件(到达尾部节点)
		{
			PrintListReversingly_Recursively(pHead->m_pNext);	//递推公式
		}
		cout << pHead->m_nValue << ",";	//打印节点信息
	}
}

void test01()
{
	ListNode* pHead  = NULL;
    ListNode* pNode1 = NULL;
    ListNode* pNode2 = NULL;
    ListNode* pNode3 = NULL;


    pHead = (ListNode*)malloc(sizeof(ListNode));
    pNode1 = (ListNode*)malloc(sizeof(ListNode));
    pNode2 = (ListNode*)malloc(sizeof(ListNode));
    pNode3 = (ListNode*)malloc(sizeof(ListNode));

	if (pHead == NULL || pNode1 == NULL || pNode2 == NULL || pNode3 == NULL)
	{
		cout << "malloc fail" << endl;
		return ;
	}

	pHead->m_nValue = 0;
	pHead->m_pNext  = pNode1;

	pNode1->m_nValue = 1;
	pNode1->m_pNext  = pNode2;

	pNode2->m_nValue = 2;
	pNode2->m_pNext  = pNode3;

	pNode3->m_nValue = 3;
	pNode3->m_pNext  = NULL;

	cout << "方法1：";
	PrintListReversingly_Iteratively(pHead);	//方法1
	cout << "方法2：";
	PrintListReversingly_Recursively(pHead);	//方法2
	cout << endl;
}

int main(int argc, char const *argv[])
{
	test01();
	return 0;
}

 

4 运行