二次开发有没有前途_外贸流程英文_外链网站推荐_友情链接网

编号为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;
}