单向循环链表的约瑟夫环问题

编号为1到n的n个人围成一圈。从编号为1的人开始报数，报到m的人离开。下一个人继续从1开始报数。n-1轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;

1、创建结点

与链表的创建节点相同。

//创建节点
ListNode* CreateNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

2、创建链表

将节点之间链接成链表，需要注意的是，n个人，其实就化作n个节点，将其连接成一个环形链表。

//连接节点创建链表
ListNode* CreateList(int n)
{
    ListNode* phead, * ptail;
    int i = 1;
    ptail = phead = CreateNode(i++);
    while (i <= n)
    {
        ptail->next = CreateNode(i++);
        ptail = ptail->next;
    }
    //成环
    ptail->next = phead;

    return phead;
}

注意链接到最后，成环需要将尾节点的next指针指向头结点。 

3、处理约瑟夫环问题

创建一个变量i用于记录节点的位置，创建cur指针遍历这个环形链表，当 i != m 时，继续遍历环形链表；当 i == m 时，我们需要将此时cur指向的节点删除，并链接cur指向节点的前一个节点和后一个节点，进行前述操作需要额外创建一个指针prev指向cur上一个节点进行操作。然后继续处理，直到该环形链表最后只剩下一个节点停止并返回该节点的值。

int JosephRing(int n, int m) {
    ListNode* head = CreateList(n);
    ListNode* cur = head;
    ListNode* prev = NULL;
    int i = 1;
    while (cur->next != cur)
    {
        if (i == m)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
            i = 1;
        }
        else
        {
            prev = cur;
            cur = cur->next;
            i++;
        }
    }
    return cur->val;
}