剑指offer-算法题练习：part3 从尾到头打印链表
时间限制：1秒空间限制：32768K 本题知识点： 链表 算法知识视频讲解 题目描述 输入一个链表，从尾到头打印链表每个节点的值。 输入描述: 输入为链表的表头 输出描述: 输出为需要打印的“新链表”的表头
解法1——deque:
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(struct ListNode* head) { deque<int> result; struct ListNode* p; p = head; while(p){ result.push_front(p->val); p=p->next; } vector<int> result2; result2.assign(result.begin(),result.end()); return result2; } }; 解法2——压栈:
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(struct ListNode* head) { vector<int> result; struct ListNode* p; p = head; while(p){ result.push_back(p->val); p=p->next; } vector<int> result2; for(auto i=result.end()-1; i!=result.begin()-1; i--){ result2.push_back(*i); }//for return result2; } }; 解法3——（ 最简单）运用链表插值函数：
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(struct ListNode* head) { vector<int> result; //deque<int> result; struct ListNode* p; p = head; while(p){ result.insert(result.begin(),p->val); p=p->next; } return result; } };
