从尾到头打印链表
方法一:
先从头到尾打印链表,然后利用直接反转即可,这样最简单
利用vector容器中的反转功能
代码如下:
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> res; while(head){ res.push_back(head->val); head = head->next; } return vector<int>(res.rbegin(),res.rend()); } };
方法二:用两个指针先将链表进行反转,在输出
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { //先将链表进行反转 ListNode *p=NULL;//存放当前节点的前一个节点 ListNode *q=head;//当前节点 ListNode *r=NULL;//存放当前节点的后一个节点‘’ // if(head==NULL) return NULL; while(q!=nullptr) { r=q->next;//先保存当前节点的指向 q->next = p;//改变当前节点的指向 p=q; q=r; } //从头到尾遍历输出 vector<int> v;//创建一个容器用来保存 while(p)//反转后的p就是链表的第一个节点 { v.push_back(p->val); p = p->next; } return v; } };
方法三:
使用数据结构--栈(先进后出)
先将链表的各个节点的数据值入栈操作,然后出栈即可。
代码注释比较清楚,在此不赘述了
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { //用栈这种数据结构,主要是使用栈先进后出的特点, //这样不会改变链表的结构,这也是剑指offer中给出的方法 stack<int>s;//创建一个栈结构 ListNode *p = head;//p通过不断的移动,依次遍历链表 vector<int> v;// while(p!=nullptr)//当节点不为空,就一直循环 { s.push(p->val);//链表数据值入栈 p = p->next; } while(!s.empty())//当栈不为空的时候, { v.push_back(s.top());//将栈顶元素依次存入Vector容器中 s.pop();//完成链表的出栈操作 } return v;//直接返回vector容器即可。打印输出链表的元素值 } };