用C++语言,在head指向的循环链表中,根据给定的报数间隔step,逐一删除节点,直到剩余step-1个节点结束,最后返回新的循环链表的头指针
时间: 2023-09-19 21:07:02 浏览: 129
以下是基于C++语言的实现:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* josephus(ListNode* head, int step) {
if (!head || head->next == head || step < 1) {
return head;
}
ListNode* cur = head;
while (cur->next != head) {
cur = cur->next;
}
int count = 0;
while (head != cur) {
if (++count == step) {
ListNode* tmp = head;
cur->next = head->next;
head = head->next;
count = 0;
delete tmp;
} else {
cur = head;
head = head->next;
}
}
return head;
}
int main() {
ListNode* head = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = head;
ListNode* newHead = josephus(head, 3);
cout << newHead->val << endl; // 输出 4
return 0;
}
```
在这个实现中,我们首先检查输入的合法性,然后遍历链表,找到链表的尾节点。接下来,我们使用计数器变量来模拟报数的过程,当计数器变量等于给定的step时,就删除当前节点并更新链表指针。最后返回新的头指针。
需要注意的是,在删除当前节点之前,我们需要将当前节点的前驱节点的next指针指向当前节点的后继节点,这样才能保证链表仍然是一个循环链表。
阅读全文