链表经典面试题之从尾到头打印单链表

本文主要是介绍链表经典面试题之从尾到头打印单链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

要求将一无头单链表的节点从尾到头打印出来。

这是一道经典的面试题，今天我们来介绍它的五种解决方法。

1 解决思路：

定义两个指针，一个指向链表头（pcur)，一个指向每次要打印的节点(pprint)。每次让pcur来遍历，代码实现如下：

//从尾到头打印单链表
void THprint2(PNode pHead){if (NULL == pHead){return;}PNode pcur = NULL;PNode pprint = NULL;while (pprint != pHead){pcur = pHead;while (pcur->_pNext != pprint){pcur = pcur->_pNext;}printf("%d", pcur->_data);pprint = pcur;}
}

但这种方法每打印一个节点就要遍历一次链表，时间复杂度为o(n^2);接受不了。

2 解决思路;

遍历一遍链表，将值存到数组里，倒着打印出来(这里就不实现了）。这种方法的时间复杂度为o(n),但空间复杂度为也为o(n)。

3 解决思路：

借助栈来实现，因为栈的特性为先进后出，所以可以遍历一遍链表，将节点push进栈，然后在pop弹出，将实现逆序打印。

4 可先将链表逆置过来，再遍历一次链表将节点打印出来，最后将链表逆置回去。

5 用递归的方法来实现（强力推荐此方法）易于理解且时间复杂度为o(n),空间复杂度也为o(n).看代码：

//从尾到头打印单链表
void THprint(PNode pHead){if (NULL == pHead){return;}THprint(pHead->_pNext);printf("%d->",pHead->_data);
}

测试用例：

#define _CRT_SECURE_NO_WARNINGS
#include "标头.h"
int main(){PNode pHead;SListInit(&pHead);SListPushBack(&pHead, 1);SListPushBack(&pHead, 2);SListPushBack(&pHead, 3);SListPushBack(&pHead, 4);SListPushBack(&pHead, 5);SListPushBack(&pHead, 6);THprint(pHead);//THprint2(pHead);getchar();return 0;
}

实验结果：