【数据结构副本篇】顺序表 链表OJ
🏝️专栏：【数据结构实战篇】
🌅主页：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 here struct 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; } }; 除了过主线任务之外，我们还要每天记得刷刷副本，做一下每日委托，这样才更快地能成长为满级大佬！！！
过两天就是计算机挑战赛啦~祝愿各位都能取得好成绩呀，加油！
