数组—链表

1.二分查找类题目

704. 二分查找

题目难度：简单用时： 7 分钟标记：完成

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid -1;
            else if (nums[mid] < target) left = mid + 1 ;
        }
        return -1;
    }
};

35.搜索插入位置

题目难度：简单用时： 5 分钟标记：完成

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0 , right = nums.size() -1;
        int mid = 0;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid -1;
            else if (nums[mid] < target) left = mid +1;
        }
        return left ;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

题目难度：中等用时： 19 分钟标记：完成

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //使用两个二分查找
        int left1 = 0,left2 = 0, right1 = nums.size() - 1,right2 = nums.size() - 1;
        //先找you边的元素 left1 - 1
        bool find = false;
        while (left1 <= right1)
        {
            int mid = (left1 + right1) / 2;
            if(nums[mid] == target)  find = true;
            if (nums[mid] <= target) left1 = mid + 1;
            else right1 = mid - 1;
        }

        //先找左边的元素 right2 + 1
        while (left2 <= right2)
        {
            int mid = (left2 + right2) / 2;
            if (nums[mid] >= target) right2 = mid - 1;
            else left2 = mid + 1;
        }

        if(find == false) return {-1,-1};
        return {right2 + 1,left1 - 1};
    }
};

69. x 的平方根

题目难度：简单用时： 28 分钟标记：完成

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        long long left = 1 ,right = x, mid = 0;
        while (left <= right)
        {
            mid= (left + right) / 2;
            if (x / mid == mid) return mid;
            else if(x / mid > mid) left = mid + 1;
            else right = mid - 1;
        }
        return right;

    }
};

367. 有效的完全平方数

题目难度：简单用时： 3 分钟标记：完成

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num < 2) return num;
        long long left = 0, right = num;
        long long mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (num == mid*mid) return true;
            else if (num  < mid * mid) right = mid - 1;
            else if (num  > mid * mid) left = mid + 1 ;
        }
        return false;
    }
};

33. 搜索旋转排序数组

题目难度：中等用时： 10 分钟标记：完成

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0,right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] == nums[left]) left++;
            else if(nums[mid] <= nums[right])
            {
                if(nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else
            {
                if(nums[mid] > target && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            }
            
        }
        return -1;
    }
};

81. 搜索旋转排序数组 II

题目难度：中等用时： 5 分钟标记：完成

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0,right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return true;
            if(nums[mid] == nums[left]) left++;
            else if(nums[mid] <= nums[right])
            {
                if(nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else
            {
                if(nums[mid] > target && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            }
            
        }
        return false;
    }
};

154. 寻找旋转排序数组中的最小值 II（未完成）

题目难度：中等用时： 15 分钟标记：未完成

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        int mins = nums[0];
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == nums[left]) left++;
            else if(nums[mid] <= nums[right]) right = mid - 1;
            else left = mid + 1;
            mins = min(mins,nums[mid]);
        }
        return mins;
    }
};

//解法2
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0 , right = nums.size() - 1;
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (nums[right] >  nums[mid]) right = mid;
            else if(nums[right] <  nums[mid]) left = mid + 1;
            else  right--;
        }
        return nums[right];
    }
};

540. 有序数组中的单一元素

题目难度：中等用时： 15 分钟标记：完成

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            //cout << mid <<endl;
            if(mid > 0 && nums[mid] == nums[mid - 1])
            {
                //右边为偶数
                if((nums.size() - 1 - mid) % 2 == 0) right = mid;
                //左边为偶数
                else left = mid + 1;
            }
            else if(mid < nums.size() - 1 && nums[mid] == nums[mid + 1])
            {
                //左边为偶数
                if(mid  % 2 == 0) left = mid;
                //右边为偶数
                else right = mid -1; 
            }
            else return nums[mid];
        }
        return nums[mid];
    }
};

240. 搜索二维矩阵 II

这道题有一个简单的技巧：我们可以从右上角开始查找，若当前值大于待搜索值，我们向左移动一位；若当前值小于待搜索值，我们向下移动一位。如果最终移动到左下角时仍不等于待搜索值，则说明待搜索值不存在于矩阵中。

题目难度：中等用时： 5 分钟标记：完成

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int raw = 0 , col = matrix[0].size() - 1;
        while (raw < matrix.size() && col >= 0)
        {
            if (matrix[raw][col] == target) return true;
            else if(matrix[raw][col] < target) raw++;
            else col--;
        }
        return false;
    }
};

2300. 咒语和药水的成功对数

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(),potions.end());
        vector<int> res;
        for(int spe:spells)
        {
            int left = 0, right = potions.size() - 1;
            //先判断是不是在中间的
            if((long)potions[left] *  spe >= success) res.push_back(potions.size());
            else if((long)potions[right] *  spe < success) res.push_back(0);
            else
            {
                while(left <= right)
                {
                    int mid = (left + right) / 2;
                    if((long)potions[mid] *  spe >= success && (long)potions[mid - 1] *  spe < success) 
                    {
                        res.push_back(potions.size() - mid);
                        break;
                    }
                    else if((long)potions[mid] *  spe < success) left = mid + 1;
                    else right = mid - 1;
                }
            }
        }
        return res;
    }
};

162. 寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1])  right = mid;
            else left = mid + 1;
        }
            return left;
    }
};

2.双指针类题目

27. 移除元素

题目难度：简单用时： 3 分钟标记：完成

//（双指针）
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast = 0,slow = 0;
        for (fast; fast < nums.size(); ++fast) {
            if (nums[fast] != val)
            {
                nums[slow++] = nums[fast];
            }
        }
        nums.resize(slow);
        return slow;
    }
};

26. 删除有序数组中的重复项

题目难度：简单用时： 20 分钟标记：完成

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int fast = 1 ,slow = 1;
        for (fast; fast < nums.size(); ++fast) {
            if (nums[fast] == nums[fast-1]) continue;
            nums[slow++] = nums[fast];
        }
        return slow--;
    }
};

283. 移动零

题目难度：简单用时： 4 分钟标记：完成

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int fast = 0 ,slow = 0;
        for (; fast < nums.size(); ++fast) {
            if (0!=nums[fast]) nums[slow++] = nums[fast];
        }
        for (int i = slow; i < nums.size(); ++i) {
            nums[i] = 0;
        }
        }
};

844. 比较含退格的字符串

题目难度：简单用时： 7 分钟标记：完成

class Solution {
    void process(string &st)
    {
        int slow = 0;
        for (int i = 0; i < st.size(); ++i) {
            if ( st[i] != '#') st[slow++] = st[i];
            else
            {
                if (slow > 0) slow--;
            }
        }
        st.resize(slow);
    }
public:
    bool backspaceCompare(string s, string t) {
        process(s);
        process(t);
        return s == t;
    }
};

977. 有序数组的平方

题目难度：简单用时： 1 分钟标记：完成

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            nums[i] = nums[i] * nums[i];
        }
        std::sort(nums.begin(), nums.end());
        return nums;
    }
};

3. 无重复字符的最长子串

题目难度：中等用时： 15 分钟标记：完成

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> umap;
        int slow = 0,count = 0,maxcount = 0;
        for (int i = 0; i < s.size(); ++i) {
            //找不到
            if (umap.find(s[i])==umap.end())
            {
                umap.insert(s[i]);
                count++;
                maxcount = max(count,maxcount);
            }
            //找到了
            else{
                while (s[slow]!=s[i])
                {
                    umap.erase(s[slow]);
                    slow++;
                }
                slow++;
                count = umap.size();

            }
        }
        return maxcount;
    }
};

一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

题目难度：中等用时： 20 分钟标记：未完成

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res_max = 0 , right = height.size() - 1, left = 0;
        while (left < right)
        {
            res_max = max(res_max,(right - left) * min(height[left],height[right]));
            if(height[left] < height[right])left++;
            else right--;
        }
        return res_max;
    }
};

1004. 最大连续1的个数 III

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left=0 ,right = 0, res=0; 
        while(left < nums.size() && right < nums.size()) {
            if(nums[right] || k ) nums[right++]? : k--;
            else nums[left++]? : right++;
            res = max(res , right - left);
            }
        return res;
    }
};

3.滑动窗口（双指针）

209. 长度最小的子数组

题目难度：中等用时：18 分钟标记：完成

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min_count = INT_MAX,fast = 0 ,slow = 0,sum = 0;
        for (; fast < nums.size(); ++fast) {
            sum+=nums[fast];
            while (sum >= target)
            {
                min_count = min(fast - slow + 1 , min_count);
                sum-=nums[slow++];
            }
        }
        if (min_count == INT_MAX) return 0;
        return min_count;
    }
};

904. 水果成篮

题目难度：中等用时：35 分钟标记：未完成

//904. 水果成篮
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
       int left =0,right = 0,ans = 0;
       int ln=fruits[left],rn=fruits[right]; //篮子一号和二号
       while(right < fruits.size())
       {
            if(fruits[right] == rn || fruits[right] == ln){//属于篮子某个种类
                ans = max(ans,right + 1 - left);  //更新结果，每次取一个数就更新一下
                right++;
            }else{//如果遇到第三种，把慢指针移动到快指针前一步，该步的水果种类必然不同于快指针，此时慢指针慢慢回退齐所有的连续同类。（秒啊）
                left = right - 1;  //取到第三种则移动左标到right -1
                ln = fruits[left]; //更新第一个篮子
                while(left >= 1 && fruits[left - 1] == ln) left--;
                rn = fruits[right];
                ans = max(ans,right + 1 - left);
            }
       }
        return ans;
    }
};

59. 螺旋矩阵 II

题目难度：中等用时：24 分钟标记：未完成

//59. 螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int> (n,0)); //初始化数组
        res[0][0] = 1;//初始化第一个元素
        int count = 2;//记数
        int j = 0 ,i = 0;
        while (count<=n*n)
        {
            while (j < n -1 && res[i][j+1] == 0) res[i][++j] = count++;//→
            while (i < n -1 && res[i+1][j] == 0) res[++i][j] = count++;//↓
            while (j > 0 && res[i][j-1] == 0) res[i][--j] = count++;//←
            while (i > 0 && res[i-1][j] == 0) res[--i][j] = count++;//↑
        }

        return res;
    }
};

54. 螺旋矩阵

题目难度：中等用时：14 分钟标记：完成

//54. 螺旋矩阵（与上一题思路相似，生成矩阵判断是否走过）
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        int i = 0 , j = 0 ,count = 1;
        int size = matrix.size() * matrix[0].size();
        vector<vector<bool>> sym(matrix.size(),vector<bool>(matrix[0].size(), false));
        vector<int> res;
        res.push_back(matrix[0][0]);
        sym[0][0] = true;
        while (count < size)
        {
            while (j < matrix[0].size() -1 && !sym[i][j+1])
            {
                res.push_back(matrix[i][++j]);
                sym[i][j]=true;
                count++;
            }
            while (i < matrix.size() -1 && !sym[i+1][j])
            {
                res.push_back(matrix[++i][j]);
                sym[i][j]=true;
                count++;
            }
            while (j > 0 && !sym[i][j-1])
            {
                res.push_back(matrix[i][--j]);
                sym[i][j]=true;
                count++;
            }
            while (i>0 && !sym[i-1][j])
            {
                res.push_back(matrix[--i][j]);
                sym[i][j]=true;
                count++;
            }
        }

        return res;
    }
};

1365.有多少小于当前数字的数字

题目难度：简单用时： 10 分钟标记：完成

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        unordered_map<int,int>umap;
        vector<int> res(nums.begin(),nums.end());
        std::sort(nums.begin(), nums.end());
        for (int i = nums.size() -1 ; i >= 0; --i) {
            umap[nums[i]] = i;
        }
        for (int i = 0; i < res.size(); ++i) {
            res[i] = umap[res[i]];
        }
        return res;
    }
};

941.有效的山脉数组

题目难度：简单用时： 10 分钟标记：完成

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size() < 3) return false;
        //从前往后
        int st = 1;
        while (st < arr.size() && arr[st] > arr[st-1])st++;
        //从后往前
        int ed = arr.size() - 2;
        while (ed >= 0 && arr[ed] > arr[ed+1])ed--;
        if (st == 1 || ed == arr.size() - 2) return false;//在原地
        if (st-1 == ed+1) return true;
        return false;
    }
};

1207.独一无二的出现次数

题目难度：简单用时： 10 分钟标记：完成

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int,int> umap;
        for (int i = 0; i < arr.size(); ++i) {
            umap[arr[i]]+=1;
        }
        unordered_set<int> uset;
        for (auto x:umap) {
            if (uset.find(x.second)!=uset.end()) return false;
            uset.insert(x.second);
        }
        return true;
    }
};

189. 旋转数组

题目难度：简单用时： 5分钟标记：完成

//有多余空间
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        vector<int> front(nums.end() - k ,nums.end());
        vector<int> back(nums.begin(),nums.end() - k);
        front.insert(front.end(),back.begin(),back.end());
        nums.assign(front.begin(),front.end());
    }
};
//方法二
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k =  k % nums.size();
        std::reverse(nums.begin(), nums.end());
        std::reverse(nums.begin(), nums.begin()+k);
        std::reverse(nums.begin()+k, nums.end());
    }
};

724.寻找数组的中心下标

题目难度：简单用时： 10分钟标记：完成

//维护左右和
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int leftsum = 0,rightsum = accumulate(nums.begin(),nums.end(),0);
        for (int i = 0; i < nums.size(); ++i) {
            rightsum-=nums[i];
            if (leftsum == rightsum) return i;
            leftsum+=nums[i];
        }
        return -1;
    }
};

922. 按奇偶排序数组II

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        //双指针
        for (int i = 0; i < nums.size(); ++i) {
            if (i % 2 != nums[i] % 2)
            {
                int r = nums.size() - 1;
                while (r >= 0 && i % 2 != nums[r] % 2) r--;
                swap(nums[i],nums[r]);
            }
        }
        return nums;
    }
};

力扣101

167. 两数之和 II - 输入有序数组

题目难度：中等用时： 20分钟标记：完成

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0 ,right = numbers.size() - 1;
        while (left < right)
        {
            if (target == numbers[right] + numbers[left]) return {left+ 1,right+1};
            else if (target > numbers[right] + numbers[left])
            {
                left++;
                continue;
            } else if (target < numbers[right] + numbers[left])
            {
                right--;
                continue;
            }
        }
        return {0,0};
    }
};

633. 平方数之和

题目难度：中等用时： 11分钟标记：完成

class Solution {
public:
    bool judgeSquareSum(int c) {
        if (c <= 2 || (int)sqrt(c) *  (int)sqrt(c)== c) return true;
        int left = 1,right = sqrt(c) ;
        while (left<= right)
        {
            long  res = (long )left*left + (long )right*right;
            cout << res << endl;
            if ((int)res == c) return true;
            else if (res > c) right--;
            else  left++;
        }
        return false;
    }
};

524. 通过删除字母匹配到字典里最长单词

题目难度：中等用时： 15分钟标记：完成

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int maxlen = 0 , index = -1;
        for (int i = 0; i < dictionary.size(); ++i) {
            int s_piont = 0 , d_point = 0;
            while (s_piont < s.size() && d_point < dictionary[i].size())
            {
                if (s[s_piont] == dictionary[i][d_point]) d_point++;
                s_piont++;
            }
            //遇到相等
            if (d_point == dictionary[i].size())
            {
                if (maxlen < dictionary[i].size())
                {
                    maxlen = dictionary[i].size();
                    index = i;
                }
                if (maxlen == dictionary[i].size() && dictionary[i] < dictionary[index])
                {
                    maxlen = dictionary[i].size();
                    index = i;
                }
            }
        }
        if (index == -1) return "";
        return dictionary[index];
    }
};

448. 找到所有数组中消失的数字

把重复出现的数字在原数组出现的位置设为负数，最后仍然为正数的位置即为没有出现过的数。

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int pose = abs(nums[i]) - 1;
            if (nums[pose] > 0) nums[pose] = -nums[pose];
        }
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) res.push_back(i+1);
        }
        return res;
    }
};

48. 旋转图像

题目难度：中等用时： 8分钟标记：完成

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //上下翻转，再镜像对称
        for (int i = 0; i < matrix.size() / 2; ++i) {
            matrix[i].swap(matrix[matrix.size() - 1 - i]);
        }
        //镜像对称
        for (int i = 0; i < matrix.size() - 1; ++i) {
            for (int j = i + 1; j < matrix[0].size(); ++j) {
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    }
};

769. 最多能完成排序的块（未完成）

从左往右遍历，同时记录当前的最大值，每当当前最大值等于数组位置时，我们可以多一次分割。为什么可以通过这个算法解决问题呢？如果当前最大值大于数组位置，则说明右边一定有小于数组位置的数字，需要把它也加入待排序的子数组；又因为数组只包含不重复的 0 到 n，所以当前最大值一定不会小于数组位置。所以每当当前最大值等于数组位置时，假设为 p，我们可以成功完成一次分割，并且其与上一次分割位置 q 之间的值一定是 q + 1 到 p 的所有数字。

题目难度：中等用时： 8分钟标记：未完成

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0 ,maxs = INT_MIN;
        for (int i = 0; i < arr.size(); ++i) {
            maxs = max(maxs ,arr[i]);
            if (i == maxs) res++;
        }
        return res;
    }
};

566. 重塑矩阵

题目难度：中等用时： 8分钟标记：完成

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        if (r * c != mat.size() * mat[0].size()) return mat;
        vector<vector<int>> res(r,vector<int>(c));
        int col = 0 , raw = 0 , count = 0;
        for (int i = 0; i < mat.size(); ++i) {
            for (int j = 0; j < mat[0].size(); ++j) {
                count = i * mat[0].size() + j;
                raw = count / c;
                col = count % c;
                res[raw][col] = mat[i][j];
            }
        }
        return res;
    }
};

4.链表

链表定义：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

203. 移除链表元素

题目难度：简单用时：15 分钟标记：完成

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL) return head;
        ListNode* prehead = new ListNode(0);
        prehead->next = head;
        ListNode* cur = prehead;
        while (cur->next)
        {
            //找到了
            if ( cur->next->val == val) cur->next = cur->next->next;
            else cur = cur->next; //没找到就是else
        }
        return prehead->next;
    }
};

707. 设计链表

题目难度：简单用时：15 分钟标记：完成

class MyLinkedList {
public:

    struct LinkNode{
        int val;
        LinkNode *next;
        LinkNode(int va):val(va),next(nullptr){}
    };

    MyLinkedList() {
        phead = new LinkNode(0); //初始化虚拟头节点
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >( size -1)) return -1;
        else
        {
            LinkNode *temp = phead->next;
            while (index--)
            {
                temp = temp->next;
            }
            return temp->val;
        }
    }

    void addAtHead(int val) { //头插法
        LinkNode *p = new LinkNode(val);
        p->next = phead->next;
        phead->next = p;
        size++;
    }

    void addAtTail(int val) {//尾插法
        LinkNode *p = new LinkNode(val);
        LinkNode *temp = phead;
        while (temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next = p;
        size++;
    }

    void addAtIndex(int index, int val) {
        LinkNode *p = new LinkNode(val);
        LinkNode *temp = phead;

        if (index < 0 || index > size ) return;
        else
        {
            while (index--)
            {
                temp = temp->next;
            }
            p->next = temp->next;
            temp->next = p;

            size++;
        }
    }

    void deleteAtIndex(int index) {
        LinkNode *temp = phead;

        if (index >= size || index < 0) {
            return;
        }
        else
        {
            while (index--)
            {
                temp = temp->next;
            }
            temp->next = temp->next->next;

            size--;
        }
    }
private:
    int size;
    LinkNode *phead;
};

206. 反转链表

题目难度：简单用时：16 分钟标记：完成

class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode* pre = NULL;
        ListNode* cur = head;
   
        while (cur)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

24. 两两交换链表中的节点

题目难度：中等用时：16 分钟标记：未完成

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

19. 删除链表的倒数第 N 个结点

题目难度：中等用时：8 分钟标记：完成

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* prehead = new ListNode*(-1,head);
        ListNode* fast = prehead;
        ListNode* slow = prehead;
        while (n--) fast =fast->next;
        while (fast->next)
        {
            fast =fast->next;
            slow =slow->next;
        }
        slow->next = slow->next->next;
        return prehead->next;
    }
};

面试题 02.07. 链表相交

题目难度：简单用时：10 分钟标记：完成

//面试题 02.07. 链表相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA=0, lenB = 0;
        ListNode* tA = headA;
        ListNode* tB = headB;
        while (tA!=NULL)
        {
            tA=tA->next;
            lenA++;
        }
        while (tB!=NULL)
        {
            tB=tB->next;
            lenB++;
        }
        //cout << lenA << " "<<lenB<<endl;

        if (lenA >= lenB)
        {
            tA = headA;
            tB = headB;
            int ca = lenA - lenB;
            while (ca--)
            {
                tA= tA->next;
            }
        } else
        {
            tA = headA;
            tB = headB;
            int cb = lenB - lenA;

            while (cb--)
            {
                tB= tB->next;
            }
            
        }
        while (tA!=tB && tA!=NULL && tB!=NULL)
        {
            tA = tA->next;
            tB = tB->next;
        }

        if (tA==NULL) return NULL;
        else{
            return tA;
        }

    }
};

141. 环形链表

题目难度：简单用时：13分钟标记：完成

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while ( fast && fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

142. 环形链表 II

题目难度：简单用时：12分钟标记：完成

如果有环，如何找到这个环的入口。也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

//142. 环形链表 II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head ;
        ListNode* slow = head;
        if (head==NULL) return NULL;
        while (fast->next!=NULL && fast->next->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                ListNode* temp = fast;
                ListNode* temp2 = head;
                while (temp!=temp2)
                {
                    temp2=temp2->next;
                    temp=temp->next;
                }
                return temp;
            }
        }
        return NULL;

    }
};

287. 寻找重复数

和上一题相似，快慢指针，第一次相遇的时候开始，让slow为0，fast为第一次相遇的地点，再次遍历，就能找到环的入口，环的入口就是重复的数。slow = nums[slow] 为移动一下，fast = nums[nums[fast]]为移动两下。

假设有这样一个样例：[1,2,3,4,5,6,7,8,9,5]。如果我们按照上面的循环下去就会得到这样一个路径：1 2 3 4 5 [6 7 8 9][6 7 8 9] [6 7 8 9] . . .这样就有了一个环，也就是 6 7 8 9。point 会一直在环中循环的前进。

这时我们设置两个一快(fast)一慢(slow)两个指针，一个每次走两步，一个每次走一步，这样让他们一直走下去，直到他们在重复的序列中相遇

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        slow = 0;
        while (true)
        {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) break;
        }
        return slow;
    }
};

234.回文链表

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        //求出链表长度
        int n = 0;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        //翻转前一半的链表
        cur = head;
        int cnt = n / 2;
        while (cnt--)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        if (n % 2 == 1) cur = cur->next;
        while (cur && pre)
        {
            if (cur->val != pre->val) return false;
            cur = cur->next;
            pre = pre->next;
        }
        return true;
    }
};

143.重排链表

题目难度：中等用时： 10分钟标记：未完成

把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表。

class Solution {
public:
    void reorderList(ListNode* head) {
        vector<ListNode*> vec;
        ListNode* cur = head;
        while (cur)
        {
            vec.push_back(cur);
            cur = cur->next;
        }

        int left = 0 , right = vec.size() - 1;
        cur = head;
        while (left < right)
        {
            cur->next = vec[left];
            cur = cur->next;
            cur->next = vec[right];
            cur = cur->next;;
            left++;
            right--;
        }
        if (left == right)
        {
            cur->next = vec[left];
            cur->next->next = NULL;
        } else cur->next = NULL;
    }
};

160. 相交链表

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA;
        ListNode *curB = headB;
        while (curA != curB)
        {
            curA = curA == nullptr ? headB:curA->next;
            curB = curB == nullptr ? headA:curB->next;
        }
        return curA;
    }
};

328. 奇偶链表

题目难度：中等用时： 11分钟标记：完成

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* curji_pre = new ListNode(0);
        ListNode* curou_pre = new ListNode(0);
        ListNode* curji = curji_pre;
        ListNode* curou = curou_pre;
        int cnt = 0;
        while (head)
        {
            if (cnt % 2 == 0)
            {
                curou->next = head;
                curou = curou->next;
            }
            else
            {
                curji->next = head;
                curji = curji->next;
            }
            head = head->next;
            cnt++;
        }
        curji->next = nullptr;
        curou->next = curji_pre->next;
        return curou_pre->next;
    }
};

148. 排序链表（归并排序）（有意义）

快速找到一个链表的中点 -- 快慢指针

题目难度：中等用时： 11分钟标记：完成

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return head;
        //找到中间节点
        ListNode* fast = head;
        ListNode* slow = head; //中间节点
        ListNode* pre = nullptr; //中间节点
        while (fast && fast->next)
        {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        ListNode* res = new ListNode(0);
        ListNode* presss = res;



        //两个有序链表的合并
        while (left && right)
        {
            if (left->val > right ->val)
            {
                presss->next = right;
                right = right->next;
            } else
            {
                presss->next = left;
                left = left->next;
            }
            presss = presss->next;
        }
        preroot->next = right == nullptr ? left:right;
        return res->next;
    }
};

2. 两数相加

题目难度：中等用时： 15分钟标记：完成

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //两个链表相加
        ListNode* pre1 = new ListNode(0,l1);
        ListNode* pre2= new ListNode(0,l2);

        int fo = 0;
        while (pre1->next && pre2->next)
        {
            int temp = (pre1->next->val + pre2->next->val + fo);
            pre1->next->val = temp % 10;
            fo = temp / 10;
            //cout << pre1->next->val << " " << fo <<endl;
            pre1 = pre1->next;
            pre2 = pre2->next;
            
        }
        if (pre2->next) pre1->next = pre2->next;
        while (pre1->next)
        {
            int temp = (pre1->next->val + fo);
            pre1->next->val = temp % 10;
            fo = temp / 10;
            pre1 = pre1->next;
        }
        if (fo) pre1->next = new ListNode(1);
        return l1;
    }
};

数组—链表

1.二分查找类题目​

154. 寻找旋转排序数组中的最小值 II（未完成）​

2.双指针类题目​

11. 盛最多水的容器（未完成）​

3.滑动窗口（双指针）​

力扣101​

769. 最多能完成排序的块（未完成）​

4.链表​

148. 排序链表（归并排序）（有意义）​

1.二分查找类题目

154. 寻找旋转排序数组中的最小值 II（未完成）

2.双指针类题目

11. 盛最多水的容器（未完成）

3.滑动窗口（双指针）

力扣101

769. 最多能完成排序的块（未完成）

4.链表

148. 排序链表（归并排序）（有意义）