一、快慢指针寻找链表中间结点边界判断头指针不存在 或者 链表无有效结点直接返回 NULL定义快慢指针快慢指针初始都指向头结点 phead循环条件pfast ! NULL pfast-pnext ! NULL快指针前进两步pfast pfast-pnext-pnext;慢指针前进一步pslow pslow-pnext;循环终止时pslow指向链表中间结点返回慢指针pslow。核心原理快慢指针法龟兔赛跑 快指针速度 2 × 慢指针速度。 快指针走到链表末尾时慢指针刚好到达中点。node_t *linklist_find_mid_1(node_t *phead) { if(phead NULL) { return NULL;} if(is_empty(phead)) { return NULL;} node_t *pfast phead; node_t *pslow phead; while(pfast!NULL pfast-pnext ! NULL) { pfast pfast-pnext-pnext; pslow pslow-pnext; } // printStu(pslow-d); return pslow; }二、查找链表倒数第 k 个节点边界判断头指针为 NULL或者链表没有有效节点直接返回 NULL。定义两个指针p1、p2都初始指向头结点 head计数器 i 置 0。第一个循环让p1先走 k 次p1 p1-pnext每次移动后判断若 p1 变为 NULL说明链表有效节点总数不足 k 个直接返回 NULL计数器 i 自增走完 k 次跳出循环。第二个循环p1、p2同时每次向后移动一格直到p1 NULL停止。循环结束p2正好指向倒数第 k 个有效节点返回 p2。node_t *linklist_find_end_k(node_t *head,int k) { if(head NULL) { return NULL;} if(is_empty(head)1) { return NULL;} node_t *p1 head; node_t *p2 head; int i 0; while(ik) { p1 p1-pnext; if(p1NULL) return NULL; i; } while(p1 ! NULL) { p1 p1-pnext; p2 p2-pnext; } return p2; }三、判断链表是否带环边界判定头指针为 NULL 或者链表没有有效结点直接返回 -1快慢指针均初始指向头结点 head循环条件pfast ! NULL pfast-pnext ! NULL快指针一次走两步pfast pfast-pnext-pnext;慢指针一次走一步pslow pslow-pnext;判断快慢指针地址是否相等若相遇证明存在环return 1退出循环代表快指针抵达链表尾部出现 NULL链表无环return 0。int linklist_has_cycle(node_t *head) { if(head NULL || is_empty(head)1) { return -1;} node_t *pfast head; node_t *pslow head; while(pfast!NULL pfast-pnext!NULL) { pfast pfast-pnext-pnext; pslow pslow-pnext; if(pfastpslow) { return 1; } } return 0; }四、链表数据倒序边界判断 头指针为空 / 无有效结点 / 仅有 1 个有效结点无需反转直接 returnhead-pnext-pnext NULL代表链表只有一个有效节点。p指向链表第一个有效结点保存待遍历起点head-pnext NULL初始化一条空的新链表while(p ! NULL)循环取出原链表节点进行头插 ①cur p锁定当前要移动的节点 ②p p-pnext提前移动 p保留后续链表地址顺序绝对不能调换 ③cur-pnext head-pnext当前节点挂载到新链表头部 ④head-pnext cur头结点更新指向新链表首节点循环结束所有节点完成头插链表反转完成。void linklist_reverse(node_t *head) { if(head NULL || is_empty(head) || head-pnext-pnext NULL) return ; node_t *p head-pnext; head-pnext NULL; while(p!NULL) { node_t * cur p; p p-pnext; cur-pnext head-pnext; head-pnext cur; } }五、链表数据冒泡排序边界判断空链表或仅存在一个有效节点无需排序函数直接返回end 标记有序区间尾部初始赋值为 NULL外层循环只要有序边界没有抵达第一个有效节点持续执行一趟冒泡将遍历指针 next 重置为链表第一个有效结点 head-pnext内层循环遍历至有序边界 end 为止比较相邻两个节点数据若前一个结点数据大于后一个交换两个结点内部存储的数据比较完成后 next 向后移动一位一趟冒泡遍历结束end 更新为本轮最后访问的节点代表该位置及后方已成有序区间不断重复冒泡过程直到有序边界抵达第一个有效节点排序完成。原始链表head → n1 (2) → n2 (5) → n3 (3) → NULL 第一轮外层循环 endNULLnext 从 n1 开始 nextn125 不成立next 移动至 n2 nextn253 成立交换链表变为 head→n1 (2)→n2 (3)→n3 (5)next 移动至 n3 内层循环结束end n3第二轮外层循环 endn3next 重置为 n1 nextn123 不成立next 移动至 n2 内层循环结束end n2第三轮外层循环 endn2next 重置为 n1 内层循环直接不执行end n1外层循环条件 end ! head-pnext 不成立循环结束。 最终链表head→n1 (2)→n2 (3)→n3 (5)void linklist_paopao_sort(node_t *head) { if(head NULL || is_empty(head) || head-pnext-pnext NULL) return ; node_t *end NULL; while(end!head-pnext) { node_t * next head-pnext; while(next-pnext!end) { if((next-d) (next-pnext-d)) { data_t temp next-d; next-d next-pnext-d; next-pnext-d temp; } next next-pnext; } end next; } }六、链表数据原地插入排序边界判断空链表或仅一个有效节点无需排序直接返回初始划分有序区、无序区 第一个有效节点作为初始有序区p_temp指向无序区第一个节点断开有序区尾部head-pnext-pnext NULL外层循环处理无序区剩余每一个节点p_temp ! NULLp_insert从 head 开始向后遍历搜寻插入位置循环条件后继节点数据小于待插入节点则继续后移p_insert退出内层循环时p_insert后方就是正确插入位置先保存p_temp-pnext防止断链丢失无序区将p_temp插入到p_insert之后更新p_temp为无序区下一个待处理节点将p_insert复位为 head保证下一轮依旧从头搜寻插入位置无序区全部节点插入有序区后排序结束。原始链表head → n1 (2) → n2 (5) → n3 (3) → NULL初始化 有序区head→n1 (2)→NULL 无序区p_temp n2 (5)第一轮循环 p_temp n2 (5) p_insert 从 head 开始查找 p_insert-pnext n1 (2)2 5循环结束插入到 n1 后方 链表有序区head→n1 (2)→n2 (5)→NULL p_temp 更新为 n3 (3)第二轮循环 p_temp n3 (3) p_insert 从头开始搜寻 p_insert-pnext n1 (2)2 3继续后移 p_insert-pnext n2 (5)5 3 不成立停止 在 n1、n2 之间插入 n3 (3) 有序区head→n1 (2)→n3 (3)→n2 (5)→NULL p_temp NULL外层循环结束最终链表 head→2→3→5void linklist_insert_sort(node_t *head) { if(head NULL || is_empty(head) || head-pnext-pnext NULL) return ; //划分链表为有序区和无序区 node_t *p_temp head-pnext-pnext; head-pnext-pnext NULL; //需要插入的位置从头开始找 node_t *p_insert head; while(p_temp ! NULL) { //从头往后找位置找到比自己小的就放在他前面 while(p_insert-pnext ! NULL p_insert-pnext-d p_temp-d) { //没找到比自己小的就一直往后找 p_insert p_insert-pnext; } //先保存无序区的第二个节点也就是temp的下一个方便下一次也从这里取出来进行插入 node_t *ptemp p_temp-pnext; //把需要插入的节点先和insert一样指向下一个节点 p_temp-pnext p_insert-pnext; //把insert的指针域指向插入的节点的地址也就是p_temp p_insert-pnext p_temp; //更新p_temp的值下一次循环继续使用 p_temp ptemp; //复位插入位置的值下一次还是从头开始找 p_insert head; } }七、链表数据选择排序边界判断空链表或仅存在一个有效节点无需排序函数直接返回p_pos指向当前需要安放最小值的位置初始为第一个有效节点外层循环只要p_pos后面仍存在未排序节点持续一轮选择搜寻p从p_pos下一个节点开始向后遍历整个无序区间内层循环依次比较后续每一个节点数据如果找到比p_pos更小的数据交换两个节点内部的数据p不断向后移动直到链表末尾一趟搜寻完成p_pos向后移动一位锁定下一个待安放最小值的位置不断重复搜寻交换直到所有位置确定最小值升序排序完成。原始链表head → n1 (2) → n2 (5) → n3 (3) → NULL第一轮 p_pos n1 (2) p 依次指向 n2 (5)、n3 (3)全部都大于 2无交换。p_pos 移动至 n2 (5)第二轮 p_pos n2 (5) p 指向 n3 (3)35交换数据 链表变为 head→n1 (2)→n2 (3)→n3 (5) p_pos 移动至 n3 (5)外层条件p_pos-pnext NULL循环结束 最终链表 head→2→3→5void linklist_select_sort(node_t *head) { if(head NULL || is_empty(head) || head-pnext-pnext NULL) return ; node_t *p_pos head-pnext; while(p_pos-pnext!NULL) { node_t *p p_pos-pnext; while(p!NULL) { if(p-d p_pos-d) { data_t temp p-d; p-d p_pos-d; p_pos-d temp; } p p-pnext; } p_pos p_pos-pnext; } }