josephus问题 循环链表

Question

/CreateList创建一个从1到n的不带头结点的循环链表，返回指向结点1的头指针/
LinkList CreateList(int n);

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

josephus问题 循环链表

你想实现一个函数 CreateList(int n)，创建一个从1到n的不带头结点的循环链表，并返回指向结点1的头指针。

这个问题可以用Josephus问题来解决。Josephus问题是指在一个环形链表中，选择每k个结点删除一次，直到链表为空。

下面是一个解决方案：

struct Node {
    int val;
    Node* next;
};

Node* CreateList(int n) {
    Node* head = new Node();
    Node* cur = head;
    for (int i = 1; i <= n; i++) {
        cur->next = new Node();
        cur = cur->next;
        cur->val = i;
    }
    cur->next = head; // 闭环
    return head->next; // 返回指向结点1的头指针
}

这个函数首先创建一个头结点，然后循环创建n个结点，并将每个结点的值设置为从1到n。最后，闭环链表，并返回指向结点1的头指针。

注意，这个解决方案假设链表的结点结构为 struct Node { int val; Node* next; };。