顺序表、单链表经典算法题分享（未完待续...)

顺序表①移除元素②合并两个有序数组。单链表①移除链表元素②反转链表③合并两个有序链表④寻找链表的中间节点待续......⑤环形链表的约瑟夫问题⑥分割链表。一顺序表算法题1移除元素链接https://leetcode.cn/problems/remove-element在不创建新数组的情况下实现val元素的移除我们采用双指针法。让源指针循环遍历所有下标元素当元素为val时是我们需要移除的我们就不管了让其等着被其他值覆盖或者不在访问范围内只让遍历的src当元素不为val时是“新数组”需要的元素就将nums[dst]nums[src]赋值完后再dstsrc继续向下。等遍历完成时以dst为分界线以[0,dst)为下标的元素构成的数组就是我们需要的“新数组”而以[dst,numsSize)为下标的元素不在访问之列返回值就是dst。如图int removeElement(int* nums, int numsSize, int val) { int src 0; int dst 0; for(src 0; srcnumsSize ; src) { if(val ! nums[src]) { nums[dst] nums[src]; dst; } } //遍历完成 return dst; }注意此方法叫“双指针法”但src、dst都是数组的下标数字不是真正的指针变量。2合并两个有序数组链接https://leetcode.cn/problems/merge-sorted-array思路①——先将num2中数据放入num1数组的后面再使用排序算法使其呈递增排列。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int i 0; for(i0;in;i) { //塞到num1的后面 nums1[im] nums2[i]; } //冒泡排序 i 0; for(i0;inm-1;i) //趟数 { int j 0; for(j 0;jmn-1-i;j) //每一趟都能排好一个数据的位置比较的次数自然就能-i { if(nums1[j]nums1[j1]) //递增 { int tmp nums1[j]; nums1[j] nums1[j1]; nums1[j1] tmp; } } } }但冒泡排序嵌套的for循环效率不高我们看看思路②。思路②——从后向前进行比较后再从后向前将数据元素放入num1数组的后方。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //定位到后方 int l1 m-1; int l2 n-1; int l3 mn-1; while(l10 l20) { //升序 if(nums1[l1]nums2[l2]) { nums1[l3--] nums1[l1--]; } else { nums1[l3--] nums2[l2--]; } } //处理l10但l20的情况 //注意是while(l20)而不是if(l20) while(l20) { nums1[l3--] nums2[l2--]; } }二单链表算法题1移除链表元素链接https://leetcode.cn/problems/remove-linked-list-elements思路①——遍历链表当遇到val节点时就移除。分支语句为三类头结点的移除、非头结点的移除以及不移除。struct ListNode* removeElements(struct ListNode* head, int val) { //思路遍历原链表将值为val的节点移除 struct ListNode* pcur head; struct ListNode* prev head; while (pcur) { //头结点的移除 if (pcur head pcur-val val) { struct ListNode* next pcur-next; free(pcur); pcur next; head pcur; } else if ( pcur-val val) { prev-next pcur-next; free(pcur); pcur prev-next; } else { prev pcur; pcur pcur-next; } } return head; }把头结点和非头结点的移除分成两种情况是因为在头结点的移除中我们需要改变head的值而无论是非头结点还是不移除的情况下头结点head的值是不变的。错误呈现struct ListNode* removeElements(struct ListNode* head, int val) { //思路遍历原链表将值为val的节点移除 struct ListNode* pcur head; struct ListNode* prev head; while (pcur) { //头结点的移除 if (pcur head pcur-val val) { struct ListNode* next pcur-next; free(pcur); pcur next; head pcur; } if ( pcur-val val) { prev-next pcur-next; free(pcur); pcur prev-next; } else { prev pcur; pcur pcur-next; } } return head; }本来应该是if......else if......else三个并列的分支语句只会选择三种情况中的一种进入但换成if....../if......else这就是两个并列的分支语句了会先判断是否要if在判断是否要进入if......else......二者中的一者。当链表中所有元素都需要移除时if....../if......else的写法就会报错。在第一个if中链表的所有节点都移除了pcurNULL再进入第二个分支if......else......中时在if的条件判断pcur-val val中要对pcur进行访问但此时pcur已经为空了。而对空指针进行访问是错误操作。思路② ⭐——创建新链表尾插值为val的节点到新链表中。代码实现typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* newHead NULL; ListNode* newTail NULL; //“新链表”的头结点、尾结点 ListNode* pcur head; while(pcur) { //需要尾插时 if(pcur-val ! val) { //新链表为空时 if(newHead NULL) { newHead newTail pcur; pcur pcur-next; newTail-next NULL; } else //链表不为空 { newTail-next pcur; newTail pcur; pcur pcur-next; newTail-next NULL; } } //不需要尾插时 else { pcur pcur-next; } } return newHead; }思路详解虽然方法叫“创建新链表法”但此处并没有真正动态申请内存仅仅只是创建了两个指针newHead和newTail我们只是把需要保留的节点串在newHead和newTail之间可以多个指针指向同一节点形成新链表链表是新的但节点不是新的。起初我们创建指针newHead和newTail并置空在创建pcur作为遍历原链表的指针在第一次遇到pcur-val ! val时newHead和newTail都要指向pcur且newTail-next要置空继续遍历pcurpcur-next。当遇到pcur-val val时不需要放入newHead和newTail之间那就继续遍历让pcurpcur-next。如果又遇见pcur-val ! valnewHead作为头结点不需要改变newTail是尾指针要再次赋值使newTail pcur但仅仅只是改动newTail的指向还不够。newHead指向原先的某次pcur而newTail指向最新的pcur首尾指针还是各自为营并没有串起来在使newTail pcur之前我们应该让newTail-next pcur。第一次插入后newTail也是新链表的头结点指针通过newTail-next我们能让头结点的后继指针指向新的要被新插入的节点。再将newTail-next置空。※注意此处不能写newHead-next pcur虽然newHead-next pcur也能让头结点的后继指针指向新的要被插入的节点但从此以后新链表只会有两个节点——头节点和最后一次被插入的节点。newTail-next可以让每个前一次被插入节点的后继指针指向要被新插入的节点但newHead-next每次都只能让头结点指向新插入的节点如果中间还有被插入的节点都会被忽略。错误呈现①②③①newHead-next pcurtypedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* newHead NULL; ListNode* newTail NULL; //“新链表”的头结点、尾结点 ListNode* pcur head; while(pcur) { //需要尾插时 if(pcur-val ! val) { //新链表为空时 if(newHead NULL) { newHead newTail pcur; pcur pcur-next; newTail-next NULL; } else //链表不为空 { newHead-next pcur; newTail pcur; pcur pcur-next; newTail-next NULL; } } //不需要尾插时 else { pcur pcur-next; } } return newHead; }注意事项里已经分析了此处只是贴出错误代码不再赘述。②能将newTail-next NULL;写在循环结束后吗typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* newHead NULL; ListNode* newTail NULL; //“新链表”的头结点、尾结点 ListNode* pcur head; while(pcur) { //需要尾插时 if(pcur-val ! val) { //新链表为空时 if(newHead NULL) { newHead newTail pcur; pcur pcur-next; } else //链表不为空 { newTail-next pcur; newTail pcur; pcur pcur-next; } } //不需要尾插时 else { pcur pcur-next; } } //能将newTail-next NULL;写在循环结束后吗 newTail-next NULL; return newHead; }提交之后会报错——当原链表为空时pcur为空进不去循环直接执行newTail-next NULL可此时newTail也为空对空指针进行访问是错误操作如果我们想在循环结束之后再让newTail-next置空需要先对newTail判空。(不能对pcur判空无论原链表是否为空链表执行到newTail-next NULL时pcur都为空正确代码typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* newHead NULL; ListNode* newTail NULL; //“新链表”的头结点、尾结点 ListNode* pcur head; while(pcur) { //需要尾插时 if(pcur-val ! val) { //新链表为空时 if(newHead NULL) { newHead newTail pcur; pcur pcur-next; } else //链表不为空 { newTail-next pcur; newTail pcur; pcur pcur-next; } } //不需要尾插时 else { pcur pcur-next; } } if(newTail) newTail-next NULL; return newHead; }③能将else里的如下两条语句的位置进行颠倒吗pcur pcur-next; newTail-next NULL;typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* newHead NULL; ListNode* newTail NULL; //“新链表”的头结点、尾结点 ListNode* pcur head; while(pcur) { //需要尾插时 if(pcur-val ! val) { //新链表为空时 if(newHead NULL) { newHead newTail pcur; pcur pcur-next; newTail-next NULL; } else //链表不为空 { newTail-next pcur; newTail pcur; newTail-next NULL; pcur pcur-next; 不能调转两条语句的位置 } } //不需要尾插时 else { pcur pcur-next; } } return newHead; }提交后输出结果有误——我在VS2022里调试之后可以发现在在第二次插入2时会进入else分支语句newTail-next pcur;和newTail pcur;都没问题但我们执行newTail-next NULL;时是将pcur节点的后继指针置空了等我们再执行pcur pcur-next;时就是将NULL赋给pcur了就会跳出循环。原先的顺序中我们是先将pcur-next赋给pcur再执行newTail-next NULL;的所以不会影响到pcur的值的变动。所以颠倒语句顺序就是错的这么看来似乎将newTail-next NULL;写在循环结束后反而更方便不过也要注意好对newTail判空。2反转链表链接https://leetcode.cn/problems/reverse-linked-list思路①——创建count数出链表的节点个数反转 count/2 次。思路比较清晰但实现却很复杂我们需要让第一个节点和最后一个节点进行数据交换再从两头靠拢逐步将两头的节点数据一一交换总共要反转count/2次。从头向中间靠拢的节点数据交换是很容易的只需要借助next指针向下走就行但从后往中间靠拢的节点数据交换就很麻烦。单链表是单向的next指针只能指向后一个节点如果想找到前一个节点就需要额外处理可这又怎么处理——麻烦思路②⭐——创建新链表将原链表节点一个个头插进新链表中。这个思路和移除链表元素的第二个思路很像只不过移除链表元素我们用的是遍历尾插而此处我们用遍历头插而且思路更简单反转链表中原链表中的所有元素都需要头插并不需要再进行数据判断后决定是否要插入。依旧先明白此处也只是创建了两个新节点指针而不是真正创建了新节点。既然要遍历那就需要一个遍历指针pcur当newHead和newTail还为空时我们要做的是将pcur赋值给newHead和newTail再将newTail-next置空pcur继续向下走但此处就出了问题。我们之所以能通过pcur找到原链表的下一个指针是因为pcur对应节点的next指针指向了下一个节点但是我们在“newTail-next置空”语句中让pcur节点的next指针发生了变化pcu-next指向的不再是下一个指针了。由此提醒我们需要提前将pcur-next保存起来创建临时变量next无论是何时的插入都需要保存pcur-next和pcur遍历向下所以我们将保存语句和pcur遍历语句写在while循环内、if......else语句外。插完第一个节点后newHead、newTail不再为空。再进行插入时newHead变动成新的pcur要想让新链表能成功被串起来就必须要让新的newHead的next指针指向上一个被插入的节点。可上一个被插入的节点是什么是原先的pcur还是newTail是原先的pcur但pcur已经遍历向下了我们又去哪里找到原先的pcur呢这就又提醒我们需要将每次插入节点的上一个节点保存下来创建临时变量prev。回到再进行插入时newHead变成了新的pcurnewHead-next变成prev而prev被使用后应该随着pcur向下走也变成新的pcur然后再让pcur遍历向下这样prev和pcur就永远是前后关系。代码实现typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* newTail NULL; ListNode* newHead NULL; ListNode* prev head; //存储老pcur让newHead-next prev ListNode* pcur head; //遍历指针 ListNode* next NULL; //储存新pcur的next指针让改动后仍能让pcur next while (pcur) { //第一次头插 next pcur-next; // ListNode* next head-next; if (newHead NULL) { newHead newTail pcur; newTail-next NULL; // pcur next; } //非空头插 else { newHead pcur; newHead-next prev; prev pcur; // pcur next; } pcur next; } return newHead; }虽然只有短短不到三十行代码量但却想理清也并不容易我们来看几种常见错误。实则就是我写的时候犯的诸多错误......错误呈现①②③①忘记要存pcur-next没有创建临时指针变量nextSLTNode* reverseList(SLTNode* head) { SLTNode* pcur head; SLTNode* newHead NULL; SLTNode* newTail NULL; SLTNode* prev head; while (pcur) { //头插 if (newHead NULL) { newHead newTail pcur; newTail-next NULL; pcur pcur-next; } else { newHead pcur; newHead-next prev; prev pcur; pcur pcur-next; } } return newHead; }②在循环外写 ListNode* next head-next;typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* newTail NULL; ListNode* newHead NULL; ListNode* prev head; ListNode* pcur head; ListNode* next head-next; while (pcur) { //第一次头插 next pcur-next; if (newHead NULL) { newHead newTail pcur; newTail-next NULL; } //非空头插 else { newHead pcur; newHead-next prev; prev pcur; } pcur next; } return newHead; }当原链表为空时直接让nexthead-next就是对空指针进行访问错误操作。③在循环结束后才将newTail-next置空typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* newTail NULL; ListNode* newHead NULL; ListNode* prev head; ListNode* pcur head; ListNode* next NULL; while (pcur) { //第一次头插 next pcur-next; if (newHead NULL) { newHead newTail pcur; } //非空头插 else { newHead pcur; newHead-next prev; prev pcur; } pcur next; } newTail-next NULL; return newHead; }和第②的错误呈现的原因一致当原链表为空时不进入循环newTail本身就为空指针newTail-next的操作同样是访问了空指针错误操作。思路③——创建三个临时指针变量遍历改变原链表的指针指向。代码实现typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { if(head NULL) return head; ListNode* l1 NULL; ListNode* l2 head; ListNode* l3 head-next; ListNode* newHead NULL; ListNode* newTail NULL; while (l3) { l2-next l1; l1 l2; l2 l3; l3 l3-next; } //漏了一个尾结点 l2-next l1; return l2; }思路详解与第二种思路相比只是说没有把创建新头尾节点摆到明面上来说但是思想是一致的都是遍历原链表改变各个节点的next指针的指向从让原链表反着来。创建三个临时指针变量l1、l2、l3l1指向空l2指向原链表的头结点l3指向头结点的下一个节点基本逻辑是让l2的next指针指向l1再将l2赋给l1再将l3赋给l2最后让l3向后走l3l3-next遍历完原链表从而实现链表的反转。细节答疑①为什么循环的条件是 l3 先把循环条件当做l3在循环的最后一轮l1指向了倒数第二个节点l2指向了尾结点l3则是指向了NULL如果此时循环还继续那么l1会指向尾结点l2会指向NULLl3l3-next可是此时l3已经为空了访问空指针错误操作。说明当l3为空时就应该要跳出循环。②为什么要额外讨论空链表的情况在定义l3是初始值为head-next如果不额外讨论空链表的情况又会出现访问空指针的操作错误。③为什么在循环结束后还会漏掉一个节点循环的最后一轮时指向倒数第二个节点的l2的next指针指向了倒数第三个节点l1然后新的l1指向了倒数第二个节点新的l2指向了尾结点l3则是指向了NULL我们还没来得及让新的l2-next指向新的l1没来得及让尾结点的next指针指向倒数第一个节点所以说漏了处理一个节点的问题。让其l2-next l1即可。并且l2指向的尾结点就是反转后链表的头结点所以返回值是l2。3合并两个有序链表链接合并两个有序链表思路①——创建新链表设立新的头尾指针newHeadnewTail进行遍历比较尾插组成新链表。尾插的关键在于第一要分空链表和非空链表的情况第二要先让原尾结点的next指针指向新的插入节点之后再调整newTail的指向不然无法使尾插的节点相连构成新链表if(list1 NULL) return list2; if(list2 NULL) return list1; ListNode* newHead NULL; ListNode* newTail NULL; ListNode* l1 list1; ListNode* l2 list2; while(l1 ! NULL l2 ! NULL) { if(l1-val l2-val ) //头插 { if( newHead NULL) { newHead newTail l1; // newTail-next NULL; } else { newTail-next l1; newTail l1; } l1 l1-next; } else { if( newHead NULL) { newHead newTail l2; // newTail-next NULL; } else { newTail-next l2; newTail l2; } l2 l2-next; } } //l1 NULL l2 NULL if(l1 NULL) { newTail-next l2; } // else 可行 if(l2 NULL) { newTail-next l1; } return newHead;错误呈现①当一个链表为空返回另一个链表的头指针的逻辑不是if.....else......。②不要在头插时让newTail-next置空会改变l1或是l2的next指针指向丢失了后面紧跟着的数据。思路②4寻找链表的中间节点链接寻找链表的中间节点思路①经典思路——快慢指针2*slow fast当fast走到尾slow就找到了中间节点。注意寻找偶数个节点的链表的中间节点指的是找中间两个的后一个节点。typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { //快慢指针 ListNode* fast head; ListNode* slow head; while(fast fast-next) { fast fast-next-next; slow slow-next; } //slow就能找到中间节点 return slow; }5环形链表的约瑟夫问题链接环形链表的约瑟夫问题6分割链表链接分割链表——未完待续——