一、找到链表的中间节点思路1计算长度法知道链表的长度通过指针走到 len/2 位置即可。node_t * linklist_find_mid(node_t *head) { // 判断head NULL // 判断是否为空链表 // 知道链表的长度 // 通过指针走到len/2位置 }思路2快慢指针法推荐核心思想快指针一次走两步慢指针一次走一步当快指针走到最后时慢指针刚好停在中间位置奇数个节点示例a→b→c→d→e→NULL初始: pfast在a, pslow在a 第1次: pfast在c, pslow在b 第2次: pfast在e, pslow在c 第3次: pfastNULL, pslow停在c中间节点偶数个节点示例a→b→c→d→e→f→NULL初始: pfast在a, pslow在a 第1次: pfast在c, pslow在b 第2次: pfast在e, pslow在c 第3次: pfast-pnextNULL, pslow停在c中间节点偏左代码实现node_t * linklist_find_mid(node_t *head) { if (head NULL) { return NULL; } if(is_empty(head) 1) { return NULL; } node_t *pfast head; node_t *pslow head; while (pfast!NULL pfast-pnext!NULL) { pfast pfast-pnext-pnext; pslow pslow-pnext; } return pslow; }二、找到链表的倒数第k个节点例如 k2即找倒数第2个节点。核心思想1.让 p1 先走 k 步2.然后让 p1 和 p2 同时往后走直到 p1 走到 NULL3.最终 p2 停的位置就是倒数第 k 个节点图示过程链表: a → b → c → d → e → NULL 步骤1: p1先走k步后p1在cp2在a还未开始 步骤2: 同时走——p1到dp2到b 步骤3: 同时走——p1到ep2到c 步骤4: 同时走——p1到NULLp2停在d → d就是倒数第2个节点代码实现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; //node_t *p1 head-pnext; //node_t *p2 head-pnext; int i 0; while (i k) { p1 p1-pnext; if (p1 NULL) return NULL; i; } while (p1!NULL) { p1 p1-pnext; p2 p2-pnext; } return p2; }三、判断链表是否有环常见的思路是使用快慢指针快指针每次走两步慢指针每次走一步如果链表有环快慢指针最终会相遇如果无环快指针会先走到 NULL。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 (pfast pslow) { return 1; } } return 0; }四、链表的逆序倒置思路(1) 将链表拆分拆分成一个有头的空链表和一个无头链表。node_t *p head-pnext; // p 指向首节点 head-pnext NULL; // 有头链表变成空链表拆分后: head → NULL 有头空链表 p → a → b → c → d → e → NULL 无头链表(2) 通过 p 拿到每个节点往空链表中进行头插每头插一个节点无头链表就少一个节点直到无头链表为空逆序完成。代码实现void linklist_reverse(node_t *head) { if (head NULL || is_empty(head) 1 || 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; //p往后走 } }五、链表排序基本前提if (head NULL) return; if (is_empty(head)) return; if (head-pnext-pnext NULL) // 只有一个节点不需要排序 return;1. 选择排序思想给合适的位置选择合适的数。数组版参考for (i 0; i len-1; i) // 位置 { for (j i1; j len; j) // 找最小值 { if (a[i] a[j]) // 当前位置的值和后面的值比较 { 交换; } } }链表版——交换数据域实现void linklist_select_sort(node_t *head) { if (head NULL || is_empty(head) 1 || head-pnext-pnext NULL) { return ; } node_t *p_pos head-pnext; while(p_pos-pnext ! NULL) { node_t *next p_pos-pnext; while (next!NULL) { if (next-d p_pos-d) { data_t t next-d; next-d p_pos-d; p_pos-d t; } next next-pnext; } p_pos p_pos-pnext; } }2. 冒泡排序思想相邻两个元素比较小的放前大的放后。数组版参考for (i len-1; i 1; --i) // 趟数 { for (j 0; j i; j) // 一趟比较过程 { if (a[j] a[j1]) // 相邻两个数两两相比 { 交换; } } }链表版实现void linklist_bubble_sort(node_t *head) { if (head NULL || is_empty(head) 1 || head-pnext-pnext NULL) { return ; } node_t *p_pos head-pnext; node_t *end NULL; while (p_pos ! end) { node_t *next head-pnext; while (next-pnext! end) { if (next-d next-pnext-d) { data_t t next-d; next-d next-pnext-d; next-pnext-d t; } next next-pnext; } end next; } }3. 插入排序步骤第1步拆分——拿数据将首节点的下一个节点拿出来首节点设置为 NULL整个链表被划分为有序区和无序区。node_t *p_temp phead-pnext-pnext; // 从第二个节点开始拿 phead-pnext-pnext NULL; // 首节点设为NULL形成有序区第2步找位置node_t *p_insert phead; // 起始位置从头节点开始注意因为单向链表方向单一的特性插入时必须知道待插入位置的前一个节点。比较条件p_insert-pnext-data data继续往后找结束条件p_insert-pnext-data data找到了插入位置p_insert-pnext NULL找到尾部第3步插入p_temp-pnext p_insert-pnext; p_insert-pnext p_temp;注意p_temp 整个节点要被修改修改前应该先保存其地址不然后面的节点就断开了找不到了。完整代码实现void linklist_insert_sort(node_t *head) { if (head NULL || is_empty(head) 1 || head-pnext-pnext NULL) { return ; } //step1 链表被划分为 有序区 和 无序区 node_t *p_temp head-pnext-pnext; head-pnext-pnext NULL; while (p_temp!NULL) { //step2 拿数据 找位置 node_t *next p_temp; p_temp p_temp-pnext; node_t *p_insert head; while (p_insert-pnext! NULL p_insert-pnext-d next-d) { p_insert p_insert-pnext; } next-pnext p_insert-pnext; p_insert-pnext next; } }