一道简单的链表翻转输出到的问题，开始使用 C++ 解题。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：0 <= 链表长度 <= 10000

直觉

方法1

使用stack并调用内建reverse方法或者自写逻辑，以遍历输出stack内容。

方法2

不用stack，第一次扫描获得链表长度并声明lsit，第二次扫描将val逆向填入之前声明的中list。

方法3

不用stack，只用一个额外空间（必须使用，题目要求返回一个list），第一次扫描基于双指针将链表反转，第二次扫描将反转之后的链表转化成list。

代码

C++版本

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

class Solution {
    public:
        vector<int> res;
        vector<int> reversePrint(ListNode* head) {
            // // 方法1：使用vector 并调用内建reverse方法进行逆序
            // // 在所有 C++ 提交中击败了 67.71% 的用户
            // if(head == NULL)  return res;
            // ListNode *p = head;
            // while(p!=NULL){
            //     res.push_back(p->val);  // 通过使用容器对象的 push_back() 函数，在序列的末尾添加一个元素。
            //     p = p->next;
            // }
            // // 调用<algorithm>中的reverse反转方法
            // reverse(res.begin(), res.end());  // 该方法适用于vector
            // return res;

            // // 方法1：使用stack 并 基于栈先进后出的特点遍历输出结果
            // // 在所有 C++ 提交中击败了31.86% 的用户
            // if(head == NULL)  return res;
            // ListNode *p = head;
            // stack<int> tmp_stack;
            // while(p!=NULL){
            //     tmp_stack.push(p->val);  // 可以将对象副本压入栈顶。
            //     p = p->next;
            // }
            // while(!tmp_stack.empty()){
            //     int tmp = tmp_stack.top();
            //     tmp_stack.pop();  // pop()是没有返回值的
            //     res.push_back(tmp);
            // }
            // return res;

            // // 方法2：不用stack，第一次扫描获得链表长度并声明lsit，第二次扫描将val逆向填入之前声明的中list。
            // // 在所有 C++ 提交中击败了 67.79% 的用户
            // if(head==NULL)  return res;
            // ListNode *p = head;
            // int count = 0;
            // // 第一次扫描
            // while(p!=NULL){
            //     count++;
            //     p = p->next;
            // }
            // res.resize(count);
            // // 第二次扫描，将val逆向填入之前声明的中list。
            // p = head;
            // while(p!=NULL){
            //     res[count-1] = p->val;
            //     p = p->next;
            //     count--;
            // }
            // return res;

            // 方法3：不用stack，只用一个额外空间（必须使用，题目要求返回一个list），第一次扫描基于双指针将链表反转，第二次扫描将反转之后的链表转化成list
            // 在所有 C++ 提交中击败了 67.79% 的用户
            if(head==NULL)  return res;
            // 第一次扫描
            ListNode *dummy = new ListNode(0);
            dummy->next = head;
            ListNode *pre_p = dummy;
            ListNode *p = head;
            ListNode *next_p;
            while(p!=NULL){
                next_p = p->next;
                p->next = pre_p;
                pre_p = p;
                p = next_p;
            }
            head->next = NULL;
            dummy->next = pre_p;
            // 第二次扫描
            p = dummy->next;
            while(p!=NULL){
                res.push_back(p->val);
                p = p->next;
            }
            return res;
        }
};

int main(){

    cout << "创建链表开始" << endl;
    LinkedList l1;
    vector<int> nums = { 1, 4, 3, 6, 7 };
    l1.Create(nums);
    cout << "输出Linked List创建结果" << endl;
    l1.print();

    // cout << "链表反转开始" << endl;
    // 调用LeetCode方法
    Solution su;
    vector<int> res;
    ListNode* p = l1.head;
    res = su.reversePrint(p);  // 这里返回的是一个vector<int>
    cout << "输出Linked List反转结果" << endl;
    int n = 5;
    for(int i=0; i<n; i++){
        cout << res[i] << " \a";
    }
    cout << endl;
    system("pause");
}

Python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # # 方法1：使用stack并调用内建reverse方法或者遍历输出stack内容
        # if not head: return []  # 注意这里return的是一个空list
        # p = head
        # stack = []
        # while p:
        #     stack.append(p.val)
        #     p = p.next
        # # 调用reverse
        # # stack.reverse()
        # # 或者，遍历输出stack。
        # res = []
        # while len(stack):
        #     res.append(stack.pop())
        # return res
        # return stack

        # 方法2：不用stack，第一次扫描获得链表长度并声明lsit，第二次扫描将val逆向填入之前声明的中list
        # if not head:  return []
        # res = []
        # p = head
        # count = 0
        # # 第一次扫描
        # # print("第一次扫描")
        # while p:
        #     p = p.next
        #     res.append("#")  # 加入一个占位符
        #     count += 1
        # # print("第二次扫描")
        # # 第二次扫描，将val逆向填入之前声明的中list。
        # p = head
        # while p:
        #     res[count-1] = p.val
        #     p = p.next
        #     count -= 1
        # return res

        # 方法3：不用stack，只用一个额外空间（必须使用，题目要求返回一个list），第一次扫描基于双指针将链表反转，第二次扫描将反转之后的链表转化成list
        if not head:  return []
        # 第一次扫描
        dummy = ListNode(None)
        dummy.next = head
        pre_p = dummy
        p = head
        while p:
            print(p.val)
            next_p = p.next
            p.next = pre_p
            pre_p = p
            p = next_p
        head.next = None
        dummy.next = pre_p
        # 第二次扫描
        res = []
        p = dummy.next
        while p:
            res.append(p.val)
            p = p.next
        return res