🏝️专栏：【数据结构实战篇】
🌅主页：f狐o狸x
学习其实和打游戏一样，当你觉得BOSS难打的时候就说明是你的等级和装备不够，此时就需要我们多去刷刷副本，增加一点经验，顺便爆点装备出来，提升自己，从而轻松搞定BOSS
一、移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
1.1 题目分析
这个题我们用两个指针，一个（left）指向要返回的有效数组，一个（right）遍历原来的整个数组，当right指针指向的值不等于val的时候，right指向的值赋给left，同时他俩都指向下一个，当right指向val的时候，left不动，right指向下一个
1.2 解题代码
int removeElement(int* nums, int numsSize, int val) {int left = 0;int right = 0;for(right = 0; right < numsSize; right++){if(nums[right] != val){nums[left] = nums[right];left++;}}return left;
}二、删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
2.1 题目分析
这个题和上面的想发类似，也是用双指针，left == right时left不动right++，left ！= right时，right指向的值赋值给left指向的值
2.2 解题代码
int removeDuplicates(int* nums, int numsSize) {int left = 0;int right = 1;for(right = 1; right < numsSize; right++){if(nums[left] != nums[right]){nums[++left] = nums[right];}}return left + 1;
}三、合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
3.1 题目分析
题目要求我们将num2合并到num1中，因此我们需要从后向前合并，将数组num1最后一个元素和数组num2最后一个元素比较大小，大的放进去，以此类推
3.2 解题代码
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int s1 = m - 1;int s2 = n - 1;int dst = m + n - 1;while(s1!=-1&&s2!=-1){if(nums1[s1] > nums2[s2]){nums1[dst] = nums1[s1];s1--;dst--;}else{nums1[dst] = nums2[s2];s2--;dst--;}}if(s1 == -1){while(s2 != -1){nums1[dst] = nums2[s2];dst--;s2--;}}
}四、移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
4.1 题目分析
遍历链表寻找节点，在把符合条件的节点删了就好啦
4.2 解题代码
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur = head;struct ListNode* prev = NULL;while(cur){if(cur->val != val){prev = cur;cur = cur->next;}else{if(prev == NULL){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}}return head;
}五、反转一个链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
5.1 题目分析
这个题我们用三指针来解决，一个是指向当前节点，一个指向一下个节点，一个指向上一个节点，然后再来进行反转操作
5.2 解题代码
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* next = head;struct ListNode* prev = NULL;while(cur){if(next != NULL){next = cur->next;}cur->next = prev;prev = cur;cur = next;}return prev;
}六、链表的中间节点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
6.1 题目分析
此题用快慢指针来解决，快指针一次走两步，慢指针一次走一步，这样当快指针走到空的时候，慢指针刚好走了一半
6.2 解题代码
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}七、返回倒数第k个节点
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
7.1 题目分析
这个题我们也用两个指针，让第一个指针先走k步，然后第二个指针和第一个指针同时走，当第一个指针走到空的时候，第二个指针指着的就是倒数第k个
7.2 解题代码
int kthToLast(struct ListNode* head, int k) {struct ListNode* cur = head;struct ListNode* fast = head;int i = 0;for(i = 0; i < k; i++){fast = fast->next;}while(fast){cur = cur->next;fast = fast->next;}return cur->val;
}八、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
8.1 题目分析
这题我们需要新建立一个头节点出来，然后再依次比大小，小的就先放进去
8.2 解题代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* newhead = NULL;struct ListNode* tail = NULL;if(cur1 == NULL){return cur2;}if(cur2 == NULL){return cur1;}while(cur1 && cur2){if(cur1->val > cur2->val){if(newhead == NULL){newhead = cur2;tail = newhead;cur2 = cur2->next;}else{tail->next = cur2;tail = cur2;cur2 = cur2->next;}}else{if(newhead == NULL){newhead = cur1;tail = newhead;cur1 = cur1->next;}else{tail->next = cur1;tail = cur1;cur1 = cur1->next;}}}if(cur1 == NULL){tail->next = cur2;}else{tail->next = cur1;}return newhead;
}
这个题还有一种做法，就是用哨兵位的头节点来，这样就可以忽略链表一或者链表二为空的情况啦
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail = newhead;if(cur1 == NULL){return cur2;}if(cur2 == NULL){return cur1;}while(cur1 && cur2){if(cur1->val > cur2->val){tail->next = cur2;tail = cur2;cur2 = cur2->next;}else{tail->next = cur1;tail = cur1;cur1 = cur1->next;}}if(cur1 == NULL){tail->next = cur2;}else{tail->next = cur1;}struct ListNode* head = newhead->next;free(newhead);newhead = NULL;return head;
}九、链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
9.1 题目分析
这个题需要分为两步来搞定，第一步是找到中间节点，然后将后面的节点反转过来，在来和头节点开始比较
9.2 解题代码
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* next = head;struct ListNode* prev = NULL;while(cur){if(next != NULL){next = cur->next;}cur->next = prev;prev = cur;cur = next;}return prev;
}struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid = middleNode(A);mid = reverseList(mid);struct ListNode* head = A;while(mid){if(mid->val == head->val){mid = mid->next;head = head->next;}else{return false;}}return true;}
};
除了过主线任务之外，我们还要每天记得刷刷副本，做一下每日委托，这样才更快地能成长为满级大佬！！！
过两天就是计算机挑战赛啦~祝愿各位都能取得好成绩呀，加油！
