【算法】06从尾到头打印链表

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

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

使用辅助内存空间

1. 算出链表长度
2. 创建辅助链表空间
3. 循环，从尾到头存入新的地址空间返回

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


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

    if(head == NULL)
    {
        * returnSize = 0;
        return NULL;
    }

    struct ListNode* q = head;
    while(q != NULL)	//计算链表数据个数
    {
        num++;
        q = q -> next;
    }
    * returnSize = num;

    int* p = (int*)malloc(sizeof(int) * num);    //创建新地址空间,存储反转数据
    for(int i=0; i<num; i++)
    {
        p[num-1-i] = head -> val;
        head = head -> next;
    }
    return p;
}

递归法

int* reversePrint2(struct ListNode* head, int* returnSize)
{
    if(head == NULL)
    {
        *returnSize = 0;
        return malloc(sizeof(int) * 10000);
    }
    int *ans = reversePrint(head->next, returnSize);
    ans[(*returnSize)++] = head->val;
    return ans;
}