报数问题的C++解法--暴力

解题思路:
首先，输入该循环链表，在头结点指向为空时，即链表为空时，新增节点的指向就是其本身。以后新增节点以后，指针域保存的是第一个结点的地址。其次，进行排除。设置两个指针，分别为prev和p。p是prev的后继节点。p在每次数了3之后就删除该p所指向的节点。如果不需要删除，就移动两个指针。删除之后，就可以不移动指针。最后，当p和prev再次相遇在头结点时，循环结束。因此，设置一个second变量来判断是否是刚进入循环。

注意事项:
删除之后，就可以不移动指针。

参考代码:

#include<stdc++.h>

using namespace std;

struct Node

{

int data;

Node* next;

};

void Print(Node* p)

{

int res = p->data;

cout << res << " ";

}

Node* input(Node* head,int n)

{

Node* temp = head;

//插入节点

for (int i = 1; i <= n; i++)

{

Node* newNode = new Node();

newNode->data = i;

//如果头结点是空的，就自己指向自己

if (temp->next == NULL)

{

newNode->next = newNode;

temp = newNode;

head = newNode;

}

else//以后新增节点以后，指针域保存的是第一个结点的地址。

{

temp->next = newNode;

newNode->next = head;

temp = newNode;

}

}

return temp;

}

Node* Mani(Node* head)

{

Node* prev = head->next;

Node* p = prev;

int second = 0;

int i = 1;//从1开始，第一个不用移动指针

while (1)

{

if (second == 1)

{

break;//当p和prev再次相遇在头结点时，循环结束。因此，设置一个second变量来判断是否是刚进入循环。

}

if (i == 1)

{

i++;

continue;

}

else

{

if (i % 3 == 1)//删除之后，就可以不移动指针。

{

i++;

continue;

}

else {//如果不需要删除，就移动两个指针。本身在删除之前也是需要移动指针的

prev = p;

p = p->next;

}

if (i % 3 == 0)//p在每次数了3之后就删除该p所指向的节点

{

prev->next = p->next;

delete(p);

p = prev->next;

}

}

//判断删除的条件

i++;

//如果不用删的话，就移动指针

if (prev == p)

{

second = 1;

}

}

return p;

}

int main()

{

//输入n

int n;

cin >> n;

Node* head = new Node();

head->next = NULL;

head = input(head,n);//输入该循环链表，

// Print(head);

//遍历链表，当第二次达到prev = p = head时，退出循环，输出最后的结果

head = Mani(head);

//输出链表

Print(head);

return 0;

}