题目:
算法实现:遍历环形链表,每次删除第m
个结点,直到链表中只剩下一个结点
#include <iostream>
using namespace std;
int n, m;
struct node{
int val;
node* next;
};
node* pick(node* head, int m)
{
if(head == nullptr || head->next == head || m < 1)
return head;
//前驱结点pre,pre->next = head;
node* pre = head;
while(pre->next != head)
pre = pre->next;
//数到第m个结点
int cnt = 0;
while(head != pre) //head==pre表示只剩下一个结点了
{
//如果数到第m个点就删除
if(++cnt == m)
{
pre->next = head->next;
cnt = 0;//删除结点后,cnt清零,重新数m个数
}
else
pre = pre->next;
head = pre->next; //head跟着pre移动
}
return head;
}
int main()
{
cin >> n >> m; //输入n个结点,每次操作删除第m个位置
node* head = nullptr;
node* p = nullptr;
//初始化链表,把1~n添加到链表中
for(int i = 1; i <= n; i++)
{
if(head == nullptr)
{
head = new node;
head->val = i;
head->next = nullptr;
p = head;
continue;
}
p->next = new node;
p = p->next;
p->val = i;
p->next = nullptr;
}
p->next = head;//构造循环链表,尾结点的next指针指向头结点head
//输出最后存活下来的人的编号
node* n1 = pick(head, m);
cout << n1->val << endl;
return 0;
}