题目:输入一个链表,从尾到头打印链表每个节点的值
2023-09-11 14:15:22 时间
问题描述:
输入一个链表,从尾到头打印链表每个节点的值。
输入描述:
输入为链表的表头
输出描述:
输出为需要打印的“新链表”的表头
方法一:通过借助容器vector和栈stack共同完成
解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到得结点第一个输出。这就是典型的“后进先出”,可以用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个取出节点的值,放入vector容器中。
1 //链表结构体定义 2 struct ListNode { 3 int val; 4 struct ListNode *next; 5 ListNode(int x) : 6 val(x), next(NULL) { 7 } 8 }; 9 10 class Solution { 11 public: 12 vector<int> printListFromTailToHead(struct ListNode* head) { 13 14 vector<int> result;//存储输出的节点的值 15 stack<struct ListNode*> nodes;//用栈来存储每个节点 16 17 struct ListNode* pNode = head;//从链表头开始 18 while (pNode != NULL){ //链表的所有节点全部入栈 19 nodes.push(pNode); 20 pNode = pNode->next; 21 } 22 23 while (!nodes.empty()){ //出栈:后进先出 24 pNode = nodes.top(); 25 result.push_back(pNode->val); 26 nodes.pop(); 27 } 28 return result; 29 } 30 };
方法二: 不使用容器vector,直接用print结合递归方式实现链表的反向打印
递归在本质上就是一个栈结构,于是很自然地想到用递归来实现 要实现反过来输出链表每访问到一个结点的时候, 先递归输出它后面的结点,再输出该结点自身,这样链表的输出结构就反过来了。
1 struct ListNode { 2 int val; 3 struct ListNode *next; 4 ListNode(int x) : 5 val(x), next(NULL) { 6 } 7 }; 8 9 void printListFromTailToHead(ListNode* pListHead){ 10 if(pListHead!=NULL){ 11 12 //print the next node first 13 if(pListHead->next!=NULL){ 14 printListFromTailToHead(pListHead->next); 15 } 16 17 // And then print the current node 18 print("%d",pListHead->val); 19 } 20 }
方法三: 不使用栈结构stack,直接利用翻转函数reverse()函数和容器vector
每访问到一个结点的时候,取出节点的值放入容器中,最后使用翻转函数reverse()将容器翻转。
1 struct ListNode { 2 int val; 3 struct ListNode *next; 4 ListNode(int x) : 5 val(x), next(NULL) { 6 } 7 }; 8 9 class Solution{ 10 public: 11 vector<int> printListFromTailToHead(struct ListNode* head){ 12 vector<int> result; 13 struct ListNode* pNode=head; 14 15 while(pNode!=NULL){ 16 result.push_back(pNode->val); 17 pNode=pNode->next; 18 } 19 20 reverse(result.begin(),result.end());//applying reverse() 21 return result; 22 } 23 };
相关文章
- 删除链表倒数第n个节点
- Java面向对象基础--链表的改进
- 找两个链表的公共节点
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 24 两两交换链表中的节点
- (剑指Offer)面试题57:删除链表中的重复结点
- (剑指Offer)面试题26:复杂链表的复制
- LeetCode(114): 二叉树展开为链表
- LeetCode(19):删除链表的倒数第N个节点
- 142. 环形链表 II
- Leetcode.1019 链表中的下一个更大节点
- Leetcode.剑指 Offer II 023. 两个链表的第一个重合节点
- 华为OD机试 - 单向链表中间节点(Java & JS & Python)
- C++数据结构--循环链表与双向链表
- 【华为OD机试】1043 - 从单向链表中删除指定值的节点
- 【华为OD机试 2023最新 】 单向链表中间节点(C++ 100%)
- 剑指 Offer 52. 两个链表的第一个公共节点
- 从尾到头打印链表
- LeetCode 237. 删除链表中的节点
- 【LeetCode】876.链表的中间节点
- 链表的基本概念以及静态链表和动态链表
- 第四篇:LinkedHashMap,链表和哈希的合体进化
- 双向链表list(十二)