数据结构与算法：单链表综合运用（合并、分割与约瑟夫环）

数据结构与算法：单链表综合运用

链表是 C 语言数据结构的核心内容，也是算法面试的高频考点。本文聚焦链表经典实操题型，从合并有序链表、分割链表到环形链表约瑟夫问题，由浅入深拆解解题思路，结合哨兵位、循环计数等实用技巧，通过清晰的算法原理与完整代码实现，帮助读者吃透链表操作逻辑。

一、合并两个有序链表

1.1 题目

LeetCode 合并两个有序链表

1.2 算法原理

核心： 判断大小 + 链表插入 + 建立一个哨兵位

和合并两个有序数组的思路一样，定义四个指针：

• newhead 和 newtail：新链表的头尾节点
• pcur1 和 pcur2：分别指向两个要合并的链表的头节点

技巧： 可以 malloc 一块空间让 newhead 和 newtail 指向这块空间，使其成为首元节点（哨兵位），这样在插入时可以免去链表为空情况的判断，最后返回新链表的下一个节点即可。

哨兵位： 数值域不存储有效数据，指针域存储有效地址

1.3 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* 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;
}