Day1 翻转链表+数组中重复的数字+链表中倒数第k个节点

剑指 Offer 24. 反转链表(简单) ⭐

方法一：迭代

我的方法写复杂了。
假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。
其实可以先设置一个空节点。

code.png

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

方法一：递归

又写复杂了。

image.png

注意从nk是可以找到nk+1的呀！！

Code.png

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }

剑指 Offer 03. 数组中重复的数字(简单)

方法一：遍历数组

用set，或者 unordered_map

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        set<int> hi;
        for(auto it:nums){
            if(hi.count(it)==0){
                hi.insert(it);
            }
            else return it;
        }
        return -1;

    }
};

时间复杂度：O(n)。
遍历数组一遍。使用哈希集合（HashSet），添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)。
空间复杂度：O(n)。不重复的每个元素都可能存入集合，因此占用 O(n) 额外空间。

方法二： 原地交换

因为是长度为n的数组且里面元素都在0 ~ n-1之间,故可以让0在数组索引为0的地方，1在索引为1的地方。如果遇到一个1不在索引为1的地方，且数组索引为1的值为1，说明重复。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
       int i = 0;
       for(auto it: nums){
           if(it != i)
               if(nums[it] == it) return it;
               swap(nums[it],nums[i]);   
           
           i++;
       }
       return -1;

    }
};

链表中倒数第k个节点(简单)

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* cur = head;
        int len = 0;
        while(cur){
            cur = cur->next;
            len++;
        }
        if(k>len) return nullptr;
        cur = head;
        k -=1;
        while(k--){
            cur = cur->next;
        }
        ListNode* h = head;
        while(cur->next){
            h = h->next;
            cur = cur->next;
        }
        return h;

    }