C++刷题（一）：顺序表 + 单链表
📝前言说明：
本专栏主要记录本人的基础算法学习以及刷题记录，使用语言为C++。
每道题我会给出LeetCode上的题号（如果有题号），题目，以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解，主要是个人见解，如有不正确，欢迎指正，一起进步！
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C++学习笔记，C语言入门基础，python入门基础，python刷题专栏
🎀CSDN主页 愚润泽
题目
- 88.合并两个有序数组
- 27.移除元素
- 环形链表的约瑟夫问题
- 189. 轮转数组
- 面试题17.04. 消失的数字
- 链表的回文结构
- 138. 随机链表的复制
- 142. 环形链表 II
88.合并两个有序数组
这道题的关键在于，如何讲nums2的数组元素插入nums1，因为nums1的长度为m+n，也就代表后面有空位，所以可以选择从后往前插入。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 从后往前放，一定有空位
int p = m + n - 1, p1 = m - 1, p2 = n - 1;
while(p2 >= 0)
{
if (p1 >= 0 && nums1[p1] > nums2[p2]){ // p1 等于0代表p1都排好了，剩下的填p2
nums1[p--] = nums1[p1--]; // 先使用后--，填入nums1[p1]
}
else{
nums1[p--] = nums2[p2--];
}
}
}
};
27.移除元素
转换思想：删掉值==val的 → 保留（提取）值!=val的
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
for(int x : nums){
if (x != val){
nums[i++] = x;
}
}
return i;
}
};
环形链表的约瑟夫问题
暴力做法（这题还可以动态规划，但是这里不提供）：
class Solution {
public:
int ysf(int n, int m)
{
vector<int> nums(n);
for (int i = 0; i < n; i++){
nums[i] = i;
}
int start = 0;
while(nums.size()!=1){
int out = (start + m - 1) % nums.size(); // 往后移动m-1个位置是报到m的
nums.erase(nums.begin() + out);
start = out;
}
return nums[0] + 1;
}
};
189. 轮转数组
简单做法：先复制后半部分的，再复制前半部分的，最后再把数组重新赋值回给nums
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
vector<int> nums2(n); //
int j = 0;
for (int i = n - k ;i < n;i++){
nums2[j] = nums[i];
j++;
}
for(int i = 0; i < n-k; i++){
nums2[j] = nums[i];
j++;
}
// 将新数组的元素复制回原数组
for (int i = 0; i < n; i++)
{
nums[i] = nums2[i];
}
}
};
时间复杂度：因为要遍历两次数组：O(n)，空间复杂度：要开一个跟随问题规模n的同样长的数组+三个整型（常数级）：O(n)
改进：时间复杂度：O(n)，空间复杂度O(1)的做法：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size(); // 轮转 k 次等于轮转 k % n 次
ranges::reverse(nums);
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
面试题17.04. 消失的数字
两次遍历，第一次遍历记录是否出现，第二次遍历找出没出现的
class Solution {
public:
int missingNumber(vector<int>& nums)
{
int n = nums.size();
vector<int>nums2 (n + 1, -1);
for(auto num : nums)
{
nums2[num] = 1;
}
int i = 0;
for(i = 0; i < n; i++)
{
if(nums2[i] == -1)
{
break;
}
}
return i;
}
};
链表的回文结构
不是第一次写回文这道题了，但是再写还是容易出现问题。方法：中间节点+反转链表+依次比较
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
ListNode* slow = A;
ListNode* fast = A;
while(fast!= nullptr && fast->next != nullptr) // 这判断条件的时候一定要注意
// 原则：下面能使用到的指针要避免为空，如：fast->next != nullptr
// 如果要判断 fast->next ，则前提是fast != nullptr （所以要写两个）
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;
// 找到中间节点，然后反转后半部分的链表，反转后按顺序比较
// 注意：前半部分的长度>=比后半部分长（偶数时>，因为偶数时前半部分的最后一个节点依然指向mid，画图好理解），因此比完短的即可
ListNode* pre = nullptr;
ListNode* cur = mid;
while(cur){
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
// 反转完以后，pre指向原反转链表的最后一个节点，cur指向原最后一个节点的后一个位置
ListNode* p1 = A; // 第一段链表的开始
ListNode* p2 = pre; // 第二段反转后链表的开始
while(p2 != nullptr)
{
if(p1->val != p2->val){
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}
};
138. 随机链表的复制
题解（来源于灵茶山艾府）：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) { // 这里应该是官方给漏了，实际上可以传3个参数
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr){
return nullptr;
}
for (Node*cur = head; cur; cur = cur->next->next) // 走两步才到原链表的下一个节点
{
cur->next = new Node(cur->val, cur->next, nullptr); // 这里就是能传三个参数，我也不晓得为什么
}
for (Node* cur = head; cur; cur = cur->next->next){
if(cur->random){
cur->next->random = cur->random->next; // 原链表random指向的节点的下一个节点，就是新random要指向的。
}
}
Node* new_head = head->next;
Node* cur = head;
for(; cur->next->next; cur = cur->next)
{
Node* copy = cur->next; // 记录下新链表的节点
cur -> next = cur->next->next; // 恢复原来的
copy -> next = copy -> next->next; // 连接新的
}
cur->next = nullptr;
return new_head;
}
};
最后的拆分需要注意：混合链表的顺序为：旧1，新1，旧2，新2，旧3，......，旧n，新n，nullptr，两个新节点相连时会丢失一个旧节点（旧节点同理），所以：当一开始记录了旧1和新1的位置时，应该先让旧1和旧2相连，此时不会丢失新1要连接的下一个节点的信息。
142. 环形链表 II
这道题也是第二次写了。快慢指针（这里是快的速度是慢的的两倍），快的一定会追上慢的，然后我们探索位置关系：
这次关系都推出来了，但是还是没想到最后一步，重新让头指针和慢指针一起走，必会在入环口相遇。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
while(head != slow){
head = head->next;
slow = slow->next;
}
return slow;
}
}
return nullptr;
}
};
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！