剑指offer——从尾到头打印链表节点的值

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

输入描述：输入为链表的表头

输出描述：输出为需要打印的“新链表”的表头

---

一、问题分析

---

　　初拿到这个题目时，这应该是考察单向链表这一数据结构。单向链表的遍历总是从头指针逐项遍历各个节点，现在要求从尾到头打印节点的值，我们可以在遍历时把各节点压入栈内，最后出栈打印各个节点值，即可达到要求。

　　实现之前，我们先来看看如何创建一个链表。

　　1，链表节点的数据结构定义

1 struct ListNode {
2     int val;
3     struct ListNode *next;
4     ListNode(int x) :
5         val(x), next(NULL) {
6         }
7 };

　　在链表的定义中，包含自己的整形成员（当然也可以定义为其它数据类型，如double），以及下一个节点的位置信息（next）。这里我们还定义了节点的构造函数（ListNode），方便节点的初始化。

　　2，链表的创建

　　这里我们考虑单向链表。如果通过用户输入来创建链表，我们可以进行如下操作：

　　1)创建头节点head，指向NULL。因为此时没有任何节点

　　2）为加入的节点分配空间，赋初值（如1中考虑的int类型）并指向NULL。判断head==NULL?head指向该节点：“上一节点”指向该节点

　　3）更新新加入的节点为“上一节点”

　　4）判断节点是否添加结束，若否，重复2,3,4步骤继续添加节点。

---

二、问题的解决思路

---

　　1，利用stack反转输出链表节点值

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//链表节点定义
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
        }
};

//链表从尾到头输出节点值方法实现
class Solution {
    public:
        //方法1，通过stack 这个container来实现反转链表
        vector<int> printListFromTailToHead(struct ListNode* head) {
            vector<int> result;
            if(head == NULL)
                return result;
            stack<ListNode*> reverse;
            ListNode* node = head;
            while(node != NULL) {
                reverse.push(node);
                node = node->next;
            }
            while(!reverse.empty()) {
                node = reverse.top();
                result.push_back(node->val);
                reverse.pop();
            }
            return result;
        }
        //方法2，原地反转链表，不介入其它container
        //不断的使“下一个节点”指向“前一个”节点
        vector<int> printListFromTailToHead2(struct ListNode* head) { 
            vector<int> vec; 
            ListNode *buf = head; 
            ListNode *pre = buf; 
            if(head == NULL) 
                return vec; 
            while(head->next != NULL){ 
                buf = head->next; 
                head->next = buf->next; 
                buf->next = pre; 
                pre = buf; 
            } 
            while(buf){ 
                vec.push_back(buf->val); 
                buf = buf->next; 
            } 
            return vec; 
        }
};

struct ListNode* CreateListNode(struct ListNode* head) {
    struct ListNode *p1, *p2;
    int i = 1;
    p1 = p2 = (struct ListNode*)malloc(sizeof(ListNode));
    cout << "Please input the 1st node, it's address is p1_addr = " << p1 << endl;
    cout << "And input -1 to quit.";
    cin >> (p1->val);
    p1->next = NULL;

    while (p1->val != -1) {
        if (NULL == head) {
            head = p1;
        }
        else
            p2->next = p1;
        p2 = p1;
        p1 = (struct ListNode*)malloc(sizeof(ListNode));
        ++i;
        cout << "Please input the " << i << " node," << "it's address is p" << i << "_addr = " << p1 <<endl;
        cin >> (p1->val);
    }
    free(p1);
    p2->next = NULL;
    p1 = NULL;
    cout << "End of creating ListNode." << endl;
    return head;
}

int main () {
    std::vector<int> v;
    struct ListNode* head = NULL;
    head = CreateListNode(head);

    Solution s;
    v = s.printListFromTailToHead2(head);
    for (int var : v) {
        cout << var << ' ';
    }

    //测试节点的初始化，与本题无关
    struct ListNode myListNode(100);
    cout << myListNode.val << endl;

}

　　上述程序在gcc version 6.1.0下编译通过。

　　在上面的程序中，实现反转的方法有两个：

　　1）利用stack先入后出的特性实现链表的反转

　　2）不借用其它container，不断的使“后一个”节点指向“前一个节点”来原地反转链表。下面来谈谈原地反转链表

　　2，原地反转链表

　　我们看函数printListFromTailToHead2()。首先，我们先定义两个指针(buf, pre)，并与head共同指向链表的头节点。然后，通过head->next遍历原始链表，并同时更新buf指向已经遍历到的节点(buf = head->next)，而这期间head始终指向头节点。然后，更新head—>next指向buf的下一个节点(head->next = buf->next)。接着，通过buf->next = pre, 使buf指向前一个节点，紧接着更新pre，使其指向当前节点，以便下一轮更新。

　　当head->next遍历完链表后，buf指向了原始链表最后一个节点，head->next的值变为了NULL。现在从buf开始遍历，即可反向遍历链表。