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

C++

1. 先放入vector中, 再调用reverse算法. 原地方法
2. 开辟一个stack, 然后在放入vector中. 时间复杂度O(n), 空间复杂度n
3. 递归法放入. 时间复杂度n, 空间复杂度
4. 改变链表结构

需要根据面试官的需要选择不同的算法

---

有三种解法:

1. 扫描链表,得到长度后创建数组, 按顺序放入数组后原地翻转(n + n + n/2)
2. 扫描链表, 得到长度后创建数组, 倒序放入数组(n + n + n)
3. 原地翻转链表, 同时得到长度, 创建数组并放入.(n + n)(本人方法)

然而方法三看似扫描次数最少, 但是可能操作最复杂吧, 时间属于中游水平 时间

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* reversePrint(struct ListNode* head, int* returnSize){

    if(head == NULL){ *returnSize = 0; return NULL;}
    if(head->next == NULL) {int *result = malloc(sizeof(int)); *result = head->val;*returnSize = 1;return result;}
    
    *returnSize = 1;
    struct ListNode *p1 = head, *p2 = p1->next, *p3;
    p1->next = NULL;
    while(p2)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        *returnSize += 1;
    } 
    int *result = (int*)malloc(sizeof(int) * (*returnSize));
    for(int i = 0; i<*returnSize; i++)
    {
        result[i] = p1->val;
        p1 = p1->next;
    }

    return result;
}