铅笔小新z个人主页博客专栏数据结构滴水不绝可穿石步履不休能至渊。一、顺序表经典算法题1.1 经典算法OJ题1移除元素解题思路双指针法先创建两个变量src,dst让这两个变量都指向数组首元素。如果src指向的值等于val则src若不等于则将src的值赋给dst然后srcdst。最后当src走到数组末尾时循环结束。参考代码int src 0; int dst 0; while(src numsSize) { if(nums[src] val) { src; } else { nums[dst] nums[src]; } } return dst;1.2 经典算法OJ题2合并两个有序数组从题目中我们可以知道nums1数组的大小是可以共同容纳nums1和nums2所有有效数字的所以我们有一种方法就是将nums2的数字存到nums1中但题目中要求合并后的数组按非递减顺序排列这里我就来讲一讲具体的解题思路解题思路首先定义三个变量l1, l2, l3l1指向nums1数组最后一个元素l2指向nums2数组最后一个元 素l3指向nums1数组的末尾。然后将l1和l2进行比较谁大谁就放在l3的位置然后l3--l1或者l2进行--。这样最后会出现两种情况一种是l1先走完但是l2没有走完导致l2中的数字没有完全被放在l1中。另一种是l2先走完这种情况不影响最后的结果。所以我们要在程序后面判断一下出现了哪种情况。参考代码int l1 m - 1; int l2 n - 1; int l3 nums1Size - 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--]; }二、链表经典算法题2.1 单链表经典算法OJ题1移除链表元素解题思路既然要删除某一元素我们不妨新建一个新的链表然后遍历原链表把值不为val的元素存到新的链表当中。参考代码//创建新链表 struct ListNode* newhead, *newtail; newhead newtail NULL; //遍历原链表 struct ListNode* pcur head; while(pcur) { //找值不为val的值尾插到新链表中 if(pcur-val ! val) { //判断新链表是否为空 if(newhead NULL) { newhead newtail pcur; } //新链表不为空 else { newtail-next pcur; newtail newtail-next; } } pcur pcur-next; } if(newtail) newtail-next NULL; return newhead;2.2 单链表经典算法OJ题2反转链表解题思路首先如图我们创建三个指针n1, n2, n3然后利用这三个指针分别将各个元素的指向进行反转进而完成对链表的反转。那么我们就应该让n2的next指针指向n1然后n1到n2的位置n2到n3的位置n3再向后挪一位知道n2走到最后即为NULL.参考代码//判空 if(head NULL) return head; //创建三个指针 struct ListNode* n1, n2, n3; n1 NULL, n2 head, n3 n2-next; while(n2) { n2-next n1; n1 n2; n2 n3; if(n3) n3 n3-next; } return n1;2.3 单链表经典算法OJ题3合并两个有序链表解题思路做这道题的大体思路就是我们创建一个新的链表然后遍历比较两个链表各个元素的值的大小将小的元素放在新的链表中。具体思路就是我们创建新的链表时应该先创建一个哨兵位然后将两个链表的元素以哨兵位为头依次放在其后面。创建两个变量l1, l2分别指向第一个链表和第二个链表将l1和l2指向的元素的值进行比较小的放在新链表中然后将其向后移一位再进行比较。参考代码struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode)); head-val 0; head-next NULL; struct ListNode* tail head; while(l1 l2) { if(l1-val l2-val) { tail-next l1; tail tail-next; l1 l1-next; } else { tail-next l2; tail tail-next; l2 l2-next; } } if(l2 NULL) { tail-next l1; } else { tail-next l2; } return head-next;2.4 单链表经典算法OJ题4链表的中间节点解题思路这道题简便的算法就是利用快慢指针。定义两个指针slow, fast都指向链表的第一个元素慢指针一次走一步快指针一次走两步直到fast NULL或fast-next NULL此时slow对应的元素就是中间节点。这里要特别注意的是判断循环结束的条件是fast fast-next两者不能调换位置因为如果调换位置fast走到NULL时fast-next就会报错因为不能对空指针解引用。参考代码struct ListNode* slow head; struct ListNode* fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; } return slow;2.5 单链表经典算法OJ题5分割链表解题思路我们可以创建两个新链表一个小链表用于存储小于x的节点大链表用于储存大于等于x的链表最后将小链表的尾指针的next指向大链表的第一个有效元素。参考代码//判空 if(head NULL) { return head; } //创建两个带头链表 struct ListNode* lesshead, *lesstail; struct ListNode* greaterhead, *greatertail; lesshead lesstail (struct ListNode*)malloc(sizeof(struct ListNode)); greaterhead greatertail (struct ListNode*)malloc(sizeof(struct ListNode)); //遍历原链表将原链表中的节点尾插到大小链表中 struct ListNode* pcur head; while(pcur) { //尾插到小链表中 if(pcur-val x) { lesstail-next pcur; lesstail lesstail-next; } //尾插到大链表中 else { greatertail-next pcur; greatertail greatertail-next; } pcur pcur-next; } greater-next NULL; lesstail-next greaterhead-next; return lesshead-next;2.6 循环链表经典应用环形链表的约瑟夫问题解题思路我们的分析思路根据上面的图首先我们要创建一个首尾相连的环形表然后将将prev指向末尾元素便于我们后面进行向后移动pcur指向末尾元素即首元素然后我们用count开始计数从首元素开始count 1假设报数m为2然后prev和pcur向后移动一位此时countcount m所以我们要删除pcur指向的元素怎么删除呢我们要将prev-next指向pcur-next然后free(pcur)再用pcur prev-next为pcur重新赋值直到最后剩下数字3为止此时循环结束的条件是pcur pcur-next。参考代码typedef struct ListNode LN; LN* applycapa(int i) { LN* head (LN*)malloc(sizeof(LN)); head-val i; head-next NULL; return head; } //创建带环链表 LN* createCircle(int n) { //创建头节点 LN* head applycapa(1); LN* tail head; //创建链表 for(int i 2; i n; i) { tail-next applycapa(i); tail tail-next; } tail-next head; return tail; } int ysf(int n, int m ) { LN* prev createCircle(n); LN* pcur prev-next; int count 1; while(pcur ! pcur-next) { if(count m) { prev-next pcur-next; free(pcur); pcur prev-next; count 0; } else { prev pcur; pcur pcur-next; } count; } return prev-val; }