[剑指Offer]7.从尾到头打印链表

/*********************************
*   日期：2013-10-18
*   作者：SJF0115
*   题号: 九度OJ 题目1511：从尾到头打印链表
*   来源：http://ac.jobdu.com/problem.php?pid=1511
*   结果：AC
*   来源：剑指Offer
*   总结：
**********************************/
#include
#include
#include
#include
using namespace std;

typedef struct ListNode{
int value;
struct ListNode *next;
}ListNode;

//从尾到头输出链表
int ListReverse(ListNode *head){
stack 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
*   网址：http://www.nowcoder.com/books/coding-interviews/d0267f7f55b3412ba93bd35cfa8e8035?rp=1
*   来源：剑指Offer
*   博客：
-----------------------------------------*/
#include 
#include 
#include 
using namespace std;

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

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector result;
        // 递归实现
        helper(head,result);
        return result;
    }
private:
    void helper(ListNode* head,vector &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 result = s.printListFromTailToHead(root);
    for(int i = 0;i         cout<    }//for
    return 0;
}

代码三

/*---------------------------------------
*   日期：2015-07-20
*   作者：SJF0115
*   题目: 7.从尾到头打印链表
*   结果：AC
*   网址：http://www.nowcoder.com/books/coding-interviews/d0267f7f55b3412ba93bd35cfa8e8035?rp=1
*   来源：剑指Offer
*   博客：
-----------------------------------------*/
#include 
#include 
#include 
using namespace std;

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

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector 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 result = s.printListFromTailToHead(root);
    for(int i = 0;i         cout<    }//for
    return 0;
}