单链表实战：合并、分割与约瑟夫环算法详解

二、分割链表

2.1 题目

分割链表

2.2 算法原理

创建两个新链表，分别存放小于 x 和大于等于 x 的节点。遍历完成后，将第一个链表的尾部连接到第二个链表的头部。

同样建议使用哨兵位，并将哨兵位的 next 初始化为 NULL，这样可以避免合并时一条链表为空的特殊判断。

关键点： 第二个链表（list2）的最后一个节点的 next 必须置为 NULL，防止形成死循环。

2.3 代码

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;

    // 初始化哨兵位 next 为 NULL
    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 时，让 prev 指向的元素跳过当前元素出队，即修改 prev->next 指向 phead->next。

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;
}