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

【题目来源】

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

【题目内容】

【解题思路】

思路一：遍历(执行用时：12 ms 内存消耗：7.4 MB)

• 申请最大资源的数组，逆向拷贝数据。
• 时间复杂度 O(N)
• 空间复杂度 O(N)

#define RES_MAX_SIZE 10000
int* reversePrint(struct ListNode* head, int* returnSize){
    *returnSize = 0;
    int *res = malloc(sizeof(int) * (RES_MAX_SIZE + 1));
    int *cur = res + RES_MAX_SIZE;
    while (head != 0) {
        cur--;
        *cur = head->val;
        (*returnSize)++;
        head = head->next;
    }
    return cur;
}

【学习小结】

数组比Hash性能更好

相比于HashSet，使用数组绝对会有性能的提高，主要表现在如下的两个方面：

哈希表 (HashSet) 底层是使用数组 + 链表或者红黑树组成的，而且它的数组也是用不满的，有加载因子的。所以使用数组来代替哈希表，能节省空间

哈希表在判重的时候需要经过哈希计算，还可能存在哈希冲突的情况，而使用数组则可以直接计算得到 index 的内存位置，所以使用数组访问性能更好。

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/duo-chong-jie-fa-xun-xu-jian-jin-yi-zhi-dao-zui-yo/

调整执行顺序，性能提升

判断场景先执行nums[nums[cur]]，再执行nums[cur]，触发预取，提高性能。

将满足条件概率更大的条件放到前面，可以避免大量无效判断，提高性能。