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

注：工程开发中应及时释放手动开辟的空间，养成良好的编程习惯。

二、分割链表

2.1 题目

LeetCode 分割链表

2.2 算法原理

创建两个新链表，list1 和 list2 分别存放小于 x 和大于或等于 x 的节点，最后让 list1 的尾指针指向 list2 的第一个元素即可。

注： list2 作为新链表的后半部分，最后一个节点的 next 要及时置 NULL，防止死循环。

技巧： 依旧可以使用哨兵位，并把哨兵位的 next 初始化为 NULL，可以避免合并时一条链表为空的特殊判断造成要写大量特判代码。

2.3 代码

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

struct ListNode* partition(struct ListNode* 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;
}

三、环形链表的约瑟夫问题

3.1 题目

牛客网 环形链表的约瑟夫问题

3.2 算法原理

核心： 利用循环链表 + 循环计数

定义一个指针 prev 指尾节点，一个指针 phead 指向头结点，利用一个变量 count 来循环计数，当 count == m 时让 phead 指向的当前元素出队即可。

3.3 代码

typedef struct ListNode 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;
}

int ysf(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;
}

总结

本文系统讲解了链表操作的三大经典题型：合并有序链表通过哨兵位简化插入逻辑，分割链表采用双链表分类处理，环形链表约瑟夫问题巧妙结合循环计数。每种解法均配有清晰的算法图解和完整代码实现，帮助读者深入理解链表操作的核心逻辑与实用技巧。掌握这些题型不仅能提升面试竞争力，更能培养扎实的数据结构思维。