做网站市场价,网站后台后缀名,做一个网站美工多少钱,最专业的手机网站制作目录
前言
一、基础思想#xff08;数组#xff09;
1. 移除元素 2.删除有序元素的重复项 3.合并两个有序数组
二、单链表算法
1.移除链表元素
2.翻转链表 3.合并两个有序的链表 前言
Hello,小伙伴们#xff0c;今天我们来做一个往期知识的回顾#xff0c;今天我将…目录
前言
一、基础思想数组
1. 移除元素 2.删除有序元素的重复项 3.合并两个有序数组
二、单链表算法
1.移除链表元素
2.翻转链表 3.合并两个有序的链表 前言
Hello,小伙伴们今天我们来做一个往期知识的回顾今天我将为大家讲解几道经典的顺序表和单链表算法题来帮助大家加深对单链表知识的讲解同时带领大家来感受一下数据结构的魅力
如果你喜欢我的内容的话就请不要忘了点赞评论和收藏你的支持就是我更新的动力万分感谢 好废话不多说开始我们今天的正题。
一、基础思想数组
1. 移除元素
题目链接https://leetcode.cn/problems/remove-element/description/ 我们先看这道题假设我们现在一这样的一个数组 要让我们清除掉所有 val 3的值我们想一想可以怎么做呢
1.首先我们最容易想到的就是创建一个新的数组然后遍历整个nums将val 4的值都放进
新的数组中但是我们要注意题目中的条件“你需要原地移除数字val的值”
也就是说我们不能开辟新的空间。所以这个方法行不通
2.那我们可以试试这样的方法我们首先创建两个整型变量d1 ,d2 0;
初始的状态下是这样的 我们让d1先走当 nums[d1] ! val时 nums[d2] nums[d1]; d1; d2; 然后再当nums[d1] val时直接跳过该元素后面的元素会将其覆盖掉或者是直接失去他的访问权限 我们画图理解一下 当nums[d1] val时d1直接跳过该元素直到nums[d1] ! val 或者 走到数组的末尾。 接下来直接直接拷贝到d2上
d2;
nums[d2] nums[d1] 同理最后我们就可以得到去除掉val的数组了然后我们来实现一下这个代码
int removeElement(int* nums, int numsSize, int val) {int dest 0;int src 0;for (int i 0; i numsSize; i)//遍历数组{if (nums[src] val)//排除指定的元素{src;}else//计数{nums[dest] nums[src];dest;src; }}return dest;
} 测试结果下面是我根据这个思路对代码进行优化的结果感兴趣的小伙伴一定要勇于挑战自己啊 2.删除有序元素的重复项
题目链接https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/ 这样的题遇到了我们能想出什么样的思路能
假设我们有这样的一个 数组 想要在题目中的条件下删除所有的重复项元素我们能怎么办呢 有了上一道题的基础我们不 难想到先创建两个整型变量 int d1 0; int d2 0; 我们让d1先加1 再比对nums[d1]与nums[d2];
不相等则 nums[d2] num[d1],然后 d1,直到整个循环备d1遍历一遍
好接下来我们来实现一下代码
int removeDuplicates(int* nums, int numsSize) {int dest 0;int src 1;while (src numsSize){if (nums[dest] ! nums[src] dest ! src) {
//dest ! src 可以避免相等项的重复赋值 提高效率nums[dest] nums[src];}src;}return dest 1;} 代码测试 3.合并两个有序数组
题目链接https://leetcode.cn/problems/merge-sorted-array/description/ 这道题非常的有意思 假设我们得到这两个数组 要注意最后的数组是经过nums1修改后得到的返回的数组也是nums1不能开辟新的空间
我们可以试试这样的思路
当 n and m都不小于0的时候我们让nums1[n - 1] 与nums2[m - 1]比较大小
大的就放到nums1的末尾
如图所示 在 m 小于0之前,一直循环遍历 所以·我们实现代码为
void merge(int *nums1, int n, int* nums2, int m)
{int l1 m - 1;int l2 n - 1;int l3 m n - 1;while (l1 0 l2 0){if (nums1[l1] nums2[l2]){nums1[l3--] nums1[l1--];}else{nums1[l3--] nums2[l2--];}}while (l2 0){nums1[l3--] nums2[l2--];}}
代码测试 二、单链表算法 如果还不了解单链表的同学可以先去我的另一篇博客看看单链表的知识这对数据结构的学习有很大的帮助
链接http://t.csdnimg.cn/wS03W
1.移除链表元素
题目链接https://leetcode.cn/problems/remove-linked-list-elements/description/ 这样的题我们能相处什么样的思路呢
也许我们可以试试这样解决问题 再通过比对节点中存储的数据若不要删除的节点的数据就直接尾插 否则直接跳过 在最后一定要将newtail-next NULL否则新链表依然会包含后面需要被删除的节点
接下来我们来实现一下代码 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead NULL;ListNode* newtail NULL;newhead newtail (ListNode*)malloc(sizeof(ListNode));ListNode* pcur head;while (pcur){if (pcur-val ! val){newtail-next pcur;newtail newtail-next;}pcur pcur-next;}newtail-next NULL;ListNode* ret newhead-next;
//最后要将哨兵位释放掉 避免空间的浪费free(newhead);newhead NULL;return ret;
}
代码测试1 2.翻转链表 题目链接https://leetcode.cn/problems/reverse-linked-list/description/
这样的题我们能用什么样的思路来写呢 这里作者菌就为大家实现两种思路: 1.头插原链表
什么意思呢我们画图来理解一下
这样是不是就十分的清楚了
接下来我们就可以直接来实现代码了 typedef struct ListNode LN;
LN* reverseList(struct ListNode* head) {//思路1头插原链表LN* n1, *n2;n1 n2 head;if (head NULL)//这里一定要注意处理空指针的情况也就是实例三return NULL;LN* pcur head-next;while (pcur){LN* temp pcur-next;pcur-next n1;n1 pcur;pcur temp;}n2-next NULL;return n1;
}
代码测试 接下来我们再来学习下一个思路
这个思路我们就直接在原链表的基础上修改指针的指向
我们先创建三个指针
n1 n2 n3,他们分别指向不同的位置如图 有了大致的思路我们接下来要解决一些细节性的问题
1.三个指针到最后哪一个指针才能成为成为最后修改后链表的头结点
2.三指针会出现位移差所以要注意不要出现对NULL的解引用操作
接下来我们可以来实现代码了 LN* n1, *n2, *n3;n1 NULL;n2 head;if (head NULL)//还是要注意对NULL的处理return NULL;n3 head-next;while (n2){n2-next n1;n1 n2;n2 n3;if (n3)//n3会最先走到空为了防止出现对NULL的解引用我们要添加这一步n3 n3-next;}return n1;
}
代码测试 3.合并两个有序的链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/description/ 这道题和我们上面的合并两个有序数组有异曲同工之妙。
我们还是可以用上面的数字比较以此比较插入 有了思路我们实现代码就不难了 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 NULL)//首先处理NULL指针的情况return list2;if (list2 NULL)return list1;if (list1 NULL list2 NULL)return NULL;ListNode* newhead, *newtail;newhead newtail (ListNode*)malloc(sizeof(ListNode));while (list1 list2){if (list1-val list2-val){newtail-next list1;newtail newtail-next;list1 list1-next;}else{newtail-next list2;newtail newtail-next;list2 list2-next;}}while (list1){newtail-next list1;list1 list1-next;newtail newtail-next;}while (list2){newtail-next list2;list2 list2-next;newtail newtail-next;}
//注意尾节点的next指针一定要指向NULLnewtail-next NULL;ListNode* ret newhead-next;//释放哨兵位以防空间浪费free(newhead);newhead NULL;return ret;
}
代码测试 好今天的学习就到这里我们下期再见拜拜
