算法学习记录三(C++)--->从尾到头打印链表每个节点的值

时间:2022-10-25 00:10:39

描述

  • 输入一个链表,从尾到头打印链表每个节点的值。

思路

对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n

示例一 展示每个节点的逆序打印 (栈–>C)

// 从尾到头打印链表,使用栈 
void RPrintList(ListNode * pHead)
{
std::stack<ListNode *> s;
ListNode * pNode = pHead;
while(pNode != NULL)
{
s.push(pNode);
pNode = pNode->m_pNext;
}
while(!s.empty())
{
pNode = s.top();
printf("%d\t", pNode->m_nKey);
s.pop();
}
}

示例一 展示每个节点的逆序打印 (递归–>C)

// 从尾到头打印链表,使用递归 
void RPrintList(ListNode * pHead)
{
if(pHead == NULL)
{
return;
}
else
{
RPrintList(pHead->m_pNext);
printf("%d\t", pHead->m_nKey);
}
}

示例二 本题用栈实现(C++)

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/

// 栈的方式
/*
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
// 初始化栈
stack<int>temp;
vector<int>res;
// 往栈里面push
while(head){
// 入栈
temp.push(head->val);
head = head->next;
}
// 从栈里面进行取出数据 push_back可以理解为OC里面的addObject
while(temp.size()){
// 每次都是从栈顶拿数据
res.push_back(temp.top());
// 出栈
temp.pop();
}
return res;

}
};
*/

示例二 本题用递归实现(C++)

// 递归方法一
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(head == NULL)return{};
if(head->next == NULL) return {head->val};
vector<int>res = printListFromTailToHead(head->next);
res.push_back(head->val);
return res;


}
};
*/


// 递归方法二
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int>res;
if(head != NULL){
res = printListFromTailToHead(head->next);
res.push_back(head->val);
}
return res;

}
};