反向输出链表
题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000思路
- 第一遍遍历找到一共的个数
- malloc
- 倒序赋值
代码
//反序打印链表
int* reversePrint(struct ListNode* head, int* returnSize) {
//第一遍遍历获取数目
int num = 0;
struct ListNode* temp = head;
while (temp)
{
num++;
temp = temp->next;
}
int* ret = (int*)malloc(num * sizeof(int));
memset(ret, -1, num * sizeof(int));
temp = head;
int i = 1;
while (temp)
{
ret[num - i] = temp->val;
i++;
temp = temp->next;
}
*returnSize = num;
return ret;
}复杂度分析
时间复杂度 O(n)
空间复杂度 O(n)
优秀思路
差不多跟我一样
int* reversePrint(struct ListNode* head, int* returnSize){
struct ListNode *p = head;
int n = 0;
while(p != NULL) {
p = p->next;
n++;
}
int *arr = (int *)malloc(sizeof(int) * n);
struct ListNode *q = head;
*returnSize = n;
for(int i = n - 1; i >= 0; i--){
arr[i] = q->val;
q = q->next;
}
return arr;
}