【剑指 Offer】从尾到头打印链表（栈思想）+ 数组中重复的数字（哈希映射）

1.数组中重复的数字–》链接

【解题思路】：

我们看到nums中所有的数字都在0 ~（n-1）之间，所以我们可以利用哈希映射思想，定义一个大小为n的vector（v）,数值都初始化为0，v的下标恰好对应0 ~（n-1）的每个数，然后遍历nums, nums[i]对应v下标的位置值++，即v[nums[i]]++,如果v[nums[i]]值大于一，说明在nums中出现了至少两次以上，因此返回nums[i].

代码实现：

class Solution {
    
public:
    int findRepeatNumber(vector<int>& nums) {
    
        int n=nums.size();
        vector<int> v(n,0);
        for(int i=0;i<n;i++)
        {
    
            v[nums[i]]++;
        }
        int i=0;
        for(;i<=n;i++)
        {
    
            if(v[nums[i]]>1)
            
            break;
        }
        return nums[i];
    }
};

2.从尾到头打印链表 --》链接

【解题思路1】：
其实看到这个题目的直觉就是把链表里面的数据放入一个数组中，然后将数组的数据反一下就可以.

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    vector<int> reversePrint(ListNode* head) {
    

            vector<int> m;
            while(head)
            {
    
                 m.push_back(head->val);
                 head=head->next;
            }
            vector<int> v;
            for(int i=m.size()-1;i>=0;i--)
            {
    
                v.push_back(m[i]);
            }
            return v;
    }
};

【解题思路2】：
但是这样会多定义一个数组来存储数据使得空间复杂度增加，所以不实用。看到数据进去和出来顺序反着肯定想到的就是栈了，所以我们定义一个栈先把数据押入栈中，然后在将栈的数据存储的数组中即可。

class Solution {
    
public:
    vector<int> reversePrint(ListNode* head) {
    

            vector<int> v;
            stack<int> s;
            while(head)
            {
    
                s.push(head->val);
                head=head->next;
            }
            while(!s.empty())
            {
    
                v.push_back(s.top());//取栈顶元素
                s.pop();//删栈顶元素
            }
            return v;
    }
};