W...Y的主页 ?
代码仓库分享 ?
前言：
今天我们来回顾一下顺序表与链表，针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习，这样才能巩固我们学习的内容。
话不多说，我们开始进入OJ习题训练！！！
【leetcode 27.移除元素】
OJ链接
给你一个数组 和一个值 ，你需要原地移除所有数值等于 的元素，并返回移除后数组的新长度。
numsvalval不要使用额外的数组空间，你必须仅使用 额外空间并原地修改输入数组。
O(1)元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
题目函数接口：
nums：给定数组内容。numsSize：数组长度大小。val：移除元素。
题目要求原地删除数据，不能创建任何数组，这就会使原本简单的题变复杂。那我们应该怎么办呢？
首先我们最先想到的方法是遍历数组，遇到需要删除的内容就将数组后面的元素向前挪动一位，让其覆盖。但是这种方法非常”危险“，有可能导致数组越界，也有可能删除遗漏。所以这不是个好方法。
接下来将一个比较新颖且简单的方法：
双指针： 创建两个指针变量src与dst，两个指针全部指向数组开头。如果src指向的内容不是val，将src的内容赋值给dst，然后src与dst全部向后挪动一位。反之如果src指向的内容为val，dst保持原来的位置不动，src向后挪动一位。直至src指向数组的末尾结束。
这个方法即保证没有创建任何数组空间复杂度为O(1)，也优化了暴力遍历法中时间复杂度，从O(n^2)->O(n)。
代码展示：
nt removeElement(int* nums, int numsSize, int val){ int ret = 0; int valp = 0; int n = numsSize; while(ret < numsSize) { if(nums[ret] != val) { nums[valp++] = nums[ret++]; } else ret++; } return valp; }
【leetcode 26.删除有序数组中的重复项】
OJ链接
给你一个 升序排列 的数组
nums，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。考虑
nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。- 返回
k。判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }如果所有断言都通过，那么您的题解将被通过。
题目函数接口：
nums：升序数组。numsSize：数组中元素个数。
思路：快慢双指针
分析：创建两个指针变量fast与slow
如果两个指针指向内容全部相同，fast向后挪动一位slow不变。
如果两个指针指向不同内容，先让slow向后移动一位，再将fast指向的内容赋值给slow，再将fast向后移动一位即可。
等到fast指向数组末尾时，循环结束！
代码演示：
int removeDuplicates(int* nums, int numsSize){ int fast = 1; int slow = 0; int n = numsSize; while(fast < n) { if(nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } else { fast++; } } return slow+1; }
leetcode 88.合并两个有序数组】
OJ链接
给你两个按 非递减顺序 排列的整数数组
nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你 合并
nums2到nums1中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组
nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。
题目接口函数：
nums1与nums2：两个非递减数组。nums1Size：nums1数组大小。nums2Size：nums2数组大小。m：nums1数组有效元素个数。n：nums2数组有效元素个数。
其实我们可以直接将两个数组进行归并，然后进行qsort排序直接完成。但是效率太低了，qsort函数底层原理为快速排序法，时间复杂度太高。
那有没有什么时间复杂度低的解法呢？
这道题本来可以两个数组进行比较，再开辟一个数组，两个数组元素进行比较，谁比较小就尾插到新数组中去。
但是这个题比较特殊，nums1开辟的空间比较大，可以放下两个数组的所有内容，所以我们必须将排序好的数组放入nums1中为了保证时间复杂度为O(m+n)。
但是我们可以使用这种方法的变形(三指针)。
解法：我们可以倒着比较，取大的依次从后往前插入。 创建三个指针，一个指向nums2数组末尾处，一个指向nums1有效元素末尾，还有一个指向nums1数组末尾处。
然后我们进行比较即可：
注意：当end1与end2全部结束才可以结束循环，否则会有问题。
举例：num1：【5，6，7，0，0，0】，num2：【2，5，6】
代码展示：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int end1 = m-1, end2 = n-1, end = m+n-1; while(end1 >= 0 && end2 >= 0){ if(nums1[end1] > nums2[end2]) nums1[end--] = nums1[end1--]; else nums1[end--] = nums2[end2--]; } while(end2 >= 0) nums1[end--] = nums2[end2--]; }
【leetcode 206.反转链表】
OJ链接
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
题目接口函数：
head：链表头节点
我们在反转数组时，只需要两个指针一个指向头，一个指向尾进行交换即可，最后指向中间即可结束。但是单链表没有数组的特性，不能进行逆向读取，所以这个方法行不通。
现在提供两种方法：
方法一：创建3个指针n1、n2、n3分别指向NULL、head、head->next。标记好三个位置即可进行链表反转。
让n2->next指向n1，然后n1=n2、n2=n3、n3=n3->next即可
一直循环直到n3指向NULL时循环停止结束。
代码演示： 文章来源：https://uudwc.com/A/GyNnr
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* a = NULL; struct ListNode* b = head; struct ListNode* c = NULL; if(b) c = b->next; if(head) { while(c) { a = b; b = c; c = b->next; b->next = a; } head->next = NULL; return b; } else return head;我们考虑问题就必须全面，如果链表中只有一个数则返回头指针head即可。
（头插法）方法二：
创建一个新链表头newhead，将旧链表元素挨个反向插入newhead中即可。
上述就是操作流程图！！！
代码演示：
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* cur = head; struct ListNode* newhead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; }
【leetcode 203.移除链表元素】
OJ链接
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
题目接口函数：
head：链表头节点。val：删除目标数
思路分析：移除目标元素，我们就要遍历链表进行查找。创建两个指针prev与cur，prev永远指向cur前一个节点，用来记录。
当cur遇到目标数时，我们就可以使用prev->next =cur->next，将目标数删除。直至cur指向NULL结束。
整体思路如下：
虽然看上去很简单，但是这种题的“极端”情况非常多。我们必须把这些特殊情况考虑清楚再去写程序才能保证万无一失。
如果遇到上述情况，使用prev->next =cur->next就不实用了，程序就会出错。那我们应该怎么办呢？
我们应该在使用prev->next =cur->next时就先把元素为val的干掉，让head指向不是val的元素。
下面是代码演示：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* prev = NULL, *cur = head; while(cur) { if(cur->val == val) { if(cur == head) { head = cur->next; free(cur); cur = head; } else { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } return head; }还有一种思路更清晰的方法：
创建一个新的头节点newhead，让cur遍历链表，把元素内容不是val的挪下来与newhead链接即可。
这样的思路更清晰，空间复杂度对于之前方法一没有改变，但是时间复杂度增加了。因为在newhead尾插时要找尾节点。我们可以增加一个尾指针指向newhead链表的尾节点，这样就可以优化时间复杂度。
代码演示：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head; struct ListNode* newhead = NULL, *tail = NULL; while(cur) { if(cur->val == val) { struct ListNode*der = cur; cur = cur->next; free(der); } else{ if(tail == NULL) { newhead = tail = cur; } else{ tail->next = cur; tail = tail->next; } cur = cur->next; } if(tail) { tail->next = NULL; } } return newhead; }代码中有很多极端问题需要大家去想清楚，在这里就不过多讲述了，不懂可以私信我！！！
【leetcode 876.链表的中间节点】
OJ链接
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
题目函数接口:
head：目标链表的头节点。
分析题目：这道题我们可以使用最原始的方法进行，先将链表遍历一遍求出链表长度，然后再次进行循环找出中间值即可。
但是有些公司面试会有题目限制要求，只让我们遍历一遍找出中间值。那我们应该怎么做呢？
(快慢指针)：
我们创建两个指针变量slow与fast指向链表的头节点，slow一次只移动一个节点，而fast指针一次移动两个节点。当fast指向NULL时，我们的slow节点顺理成章的就找到了中间节点。
这种类型的题目我们就可以利用速度差来达到题目要求！
代码演示：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head; struct ListNode* slow = head; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; } return slow; }
以上是本次全部内容，有错误或不同见解的希望与博主进行沟通交流，博主会继续努力将更好的博客内容带给大家，你们的三连是对博主最大的支持！！！ ❤️❤️文章来源地址https://uudwc.com/A/GyNnr
