[数据结构与算法]剑指 Offer 06. 从尾到头打印链表（C++实现）

题目

剑指 Offer 06. 从尾到头打印链表

这道题和著名的剑指 Offer 24. 反转链表的题很像，只不过这道题比反转链表的多了一个操作：即打印出链表的值;而反转链表的就单单的反转就行。

实现思路

1.递归思路极其代码实现

思路：

1. 设计一个函数：递归反转链表先，然后调整递归的代码；
2. 然后把链表的值插入到数组；
   

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v; //用来存放链表的值
		//递归得到反转后的链表
        ListNode* newHead =  reverse(head);
		//插入反转后的链表的值入数组v
        ListNode* cur =newHead;
        while(cur !=NULL){
            v.push_back(cur->val);
            cur = cur->next;
        }
        return v;
    }
private:
	//反转函数
    ListNode* reverse(ListNode* head){
		//如果链表为空或者只有一个结点，直接返回头指针
       if(head == NULL  || head->next == NULL){           
           return head;
        }
        //递归调用head->next后面的链表
        ListNode* newHead = reverse(head->next);
        //调整递归后的链表
        //head->next->next是指向最后一个结点的指针
        head->next->next = head;
        //修改最后一个结点的指针为NULL
        head->next = NULL;
        //返回新的头结点
        return newHead;
    }
};

2.头插法实现思路及其实现代码

思路：

1. 头插时候，先处理要头插数据的下一个结点，所以要保存将要头插结点的指针定义一个临时指针temp = head->next; 于此同时定义一个新指针 newHead = NULL;
2. 处理将要头插的数据：即head = newHead;
3. 处理头插前面的结点：newHead ->next = head;
4. 处理结束后：旧头结点继续往前移动 head = temp;
5. 开始插入数据入数组！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v;
        ListNode* newHead =  reverse(head);
        ListNode* cur =newHead;
        
        while(cur !=NULL){
            v.push_back(cur->val);
            cur = cur->next;
        }

        return v;
    }
private:
    ListNode* reverse(ListNode* head){

        if(head == NULL  || head->next == NULL){           
            return head;
        }
       ListNode* newHead = NULL;
       //让头指针遍历链表进行头插
       while(head !=NULL){
           ListNode* temp = head->next;
           head->next = newHead;
           newHead = head;
           head = temp;
       }           
        return newHead;
    }
};

3.栈模拟思路及其代码实现

思路：
由于栈的先进后出和这里的从尾打印链表刚好吻合，所以可以用栈来完成。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
         stack<int> stk;
        vector<int> v;
        //开始入栈
        while(head != NULL){
            stk.push(head->val);
            //链表迭代往下走
            head = head->next;
        }
        //开始出栈到数组
        while(!stk.empty()){
            v.push_back(stk.top());
            stk.pop(); //记得弹栈
        }
        return v;
    }  
};