319
[劍指Offer]7.從尾到頭打印鏈表
題目1511：從尾到頭打印鏈表
時間限製：1 秒
內存限製：128 兆
特殊判題：否
提交：1082
解決：350
- 題目描述：
-
輸入一個鏈表，從尾到頭打印鏈表每個節點的值。
- 輸入：
-
每個輸入文件僅包含一組測試樣例。
每一組測試案例包含多行，每行一個大於0的整數，代表一個鏈表的節點。第一行是鏈表第一個節點的值，依次類推。當輸入到-1時代表鏈表輸入完畢。-1本身不屬於鏈表。
- 輸出：
-
對應每個測試案例，以從尾到頭的順序輸出鏈表每個節點的值，每個值占一行。
- 樣例輸入：
-
1 2 3 4 5 -1
- 樣例輸出：
-
5 4 3 2 1
/*********************************
* 日期：2013-10-18
* 作者：SJF0115
* 題號: 九度OJ 題目1511：從尾到頭打印鏈表
* 來源：https://ac.jobdu.com/problem.php?pid=1511
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include<iostream>
#include<malloc.h>
#include<stdio.h>
#include<stack>
using namespace std;
typedef struct ListNode{
int value;
struct ListNode *next;
}ListNode;
//從尾到頭輸出鏈表
int ListReverse(ListNode *head){
stack<int> stack;
ListNode *p;
p = head->next;
//遍曆鏈表，把每個節點數值添加到棧中
while(p != NULL){
stack.push(p->value);
p = p->next;
}
//輸出棧
while(!stack.empty()){
printf("%d\n",stack.top());
stack.pop();
}
return 0;
}
int main()
{
int i,n;
//初始化
ListNode *head = (ListNode *)malloc(sizeof(ListNode));
ListNode *p;
head->next = NULL;
p = head;
while(scanf("%d",&n)!= EOF){
//n = -1一個測試用例的結束
if(n != -1){
//創建鏈表
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->value = n;
newNode->next = p->next;
p->next = newNode;
p = newNode;
}
//輸出
else{
/*p = head->next;
while(p != NULL){
printf("%d\n",p->value);
p = p->next;
}*/
//從尾到頭輸出
ListReverse(head);
//初始化
head->next = NULL;
p = head;
}
}
return 0;
}
【解析】
代碼二
/*---------------------------------------
* 日期：2015-07-20
* 作者：SJF0115
* 題目: 7.從尾到頭打印鏈表
* 結果：AC
* 網址：https://www.nowcoder.com/books/coding-interviews/d0267f7f55b3412ba93bd35cfa8e8035?rp=1
* 來源：劍指Offer
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(nullptr){}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
// 遞歸實現
helper(head,result);
return result;
}
private:
void helper(ListNode* head,vector<int> &result){
if(head){
if(head->next){
helper(head->next,result);
}//if
result.push_back(head->val);
}//if
}
};
int main(){
Solution s;
ListNode* root = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
root->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
vector<int> result = s.printListFromTailToHead(root);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<endl;
}//for
return 0;
}
代碼三
/*---------------------------------------
* 日期：2015-07-20
* 作者：SJF0115
* 題目: 7.從尾到頭打印鏈表
* 結果：AC
* 網址：https://www.nowcoder.com/books/coding-interviews/d0267f7f55b3412ba93bd35cfa8e8035?rp=1
* 來源：劍指Offer
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(nullptr){}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
ListNode* p = head;
while(p){
result.insert(result.begin(),p->val);
p = p->next;
}//while
return result;
}
};
int main(){
Solution s;
ListNode* root = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
root->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
vector<int> result = s.printListFromTailToHead(root);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<endl;
}//for
return 0;
}
最後更新：2017-04-03 14:53:45