【数据结构与算法】单链表的综合运用：1.合并两个有序链表 2.分割链表 3.环形链表的约瑟夫问题
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人等方向学习者
❄️个人专栏：《C语言》《【初阶】数据结构与算法》
✨ 永远相信美好的事情即将发生
文章目录
前言
链表是C语言数据结构的核心内容，也是算法面试的高频考点，其灵活的指针操作与逻辑构建对编程思维要求颇高。本文聚焦链表经典实操题型，从合并有序链表、分割链表到环形链表约瑟夫问题，由浅入深拆解解题思路，结合哨兵位、循环计数等实用技巧，通过清晰的算法原理与完整代码实现，帮读者吃透链表操作逻辑，夯实数据结构基础。
一、合并两个有序链表
1.1题目
链接：合并两个有序链表
1.2 算法原理
核心：判断大小 + 链表为插 + 建立一个哨兵位
和合并两个有序数组的思路一样，定义四个指针
newhead和newtail：新链表的头尾节点
pcur1和pcur2:分别指向两个要合并的链表的头节点
技巧：可以malloc一块空间让newhead和newtail指向这块空间，使其成为首元节点（哨兵位），这样在插入时可以免去链表为空情况的判断，最后返回新链表的下一个节点即可。
哨兵位：数值域不存储有效数据，指针域存储有效地址
1.3代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef structListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){ ListNode* newhead =(ListNode*)malloc(sizeof(ListNode)); ListNode* pcur1 = list1;; ListNode* pcur2 = list2; ListNode*newtail = newhead; newtail->next = NULL;while(pcur1 && pcur2){if(pcur1->val <= pcur2->val){ newtail->next = pcur1; newtail = newtail->next; pcur1 = pcur1->next;}else{ newtail->next = pcur2; newtail = newtail->next; pcur2 = pcur2->next;}}//为遍历完的链表直接接上新链表尾部节点if(pcur1) newtail->next = pcur1;if(pcur2) newtail->next = pcur2;return newhead->next;}注：大家也可以free掉我们手动开辟的节点空间来养成良好的编程习惯，因为这是算法题，在程序执行完后会会自动回收笔者主要讲解思路，就不主动free但大家在写工程时不要的空间要及时释放养成良好编程习惯
二、分割链表
2.1题目
链接：分割链表
2.2 算法原理
创建两个新链表，list1和list2分别存放小于x和大于或等于x的节点，最后让list1的尾指针指向list2的第一个元素即可。
注：list2作为新链表的后半部分，最后一个节点的next要及时置NILL,防止死循环
技巧：依旧可以使用哨兵位，并把哨兵位的next初始化为NULL可以避免合并时一条链表为空的特殊判断造成要写大量特判代码。
2.3代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef structListNode ListNode;structListNode*partition(structListNode* head,int x){if(head == NULL)return head;//指向小于x链表的头节点 ListNode* list1 =(ListNode*)malloc(sizeof(ListNode)); ListNode* tail1 = list1;//指向大于x链表的头节点 ListNode* list2 =(ListNode*)malloc(sizeof(ListNode)); ListNode* tail2 = list2;//防止单个节点链表出现非法解引用 list1->next = NULL; list2->next = NULL; ListNode* pcur = head;while(pcur){if(pcur->val < x){ tail1->next = pcur; tail1 = tail1->next;}else{ tail2->next = pcur; tail2 = tail2->next;} pcur = pcur->next;} tail1->next = list2->next;//防止死循环 tail2->next = NULL;return list1->next;}注：大家也可以free掉我们手动开辟的节点空间来养成良好的编程习惯，因为这是算法题，在程序执行完后会会自动回收笔者主要讲解思路，就不主动free但大家在写工程时不要的空间要及时释放养成良好编程习惯
三、环形链表的约瑟夫问题
3.1题目
链接：环形链表的约瑟夫问题
3.2 算法原理
核心：利用循环链表 + 循环计数
定义一个指针v指尾节点，一个指针指向头结点，利用一个变量s来循环技术，当s == m时让h指向的当前元素出队即可
3.3代码
typedef structListNode ListNode;//创建节点 ListNode*BuyNode(int x){ ListNode* newnode =(ListNode*)malloc(sizeof(ListNode)); newnode->val = x; newnode->next = NULL;return newnode;}//创建环形链表 ListNode*CyclicList(int n){ ListNode* head =BuyNode(1); ListNode* tail = head;for(int i =2;i <= n;i++){ tail->next =BuyNode(i); tail = tail->next;} tail->next = head;return tail;}intysf(int n,int m ){ ListNode* prev =CyclicList(n); ListNode* phead = prev->next;int count =1;//计数while(phead != prev){if(count == m){ prev->next = phead->next;free(phead); phead = prev->next; count =1;}else{ prev = phead; phead = phead->next; count++;}}return phead->val;}总结与每日励志
✨本文系统讲解了链表操作的三大经典题型：合并有序链表通过哨兵位简化插入逻辑，分割链表采用双链表分类处理，环形链表约瑟夫问题巧妙结合循环计数。每种解法均配有清晰的算法图解和完整代码实现，帮助读者深入理解链表操作的核心逻辑与实用技巧。掌握这些题型不仅能提升面试竞争力，更能培养扎实的数据结构思维。坚持每日练习，保持对算法的热情与专注，终将在编程之路上收获成长与突破。永远相信美好的事情即将发生！
