LeetCode 1823. 找出游戏的获胜者
原题链接
中等
作者:
胡歌-此生不换
,
2022-09-24 22:42:04
,
所有人可见
,
阅读 98
约瑟夫环问题(单向循环链表解决)
class Solution {
public:
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
int findTheWinner(int n, int k)
{
if(n == 1) return 1; // 特殊情况,特殊判断哦
ListNode* head = nullptr, *p = nullptr;
p = head;
int i = 1;
int num = n;
while(num--)
{
auto node = new ListNode(i++);
if(head == nullptr)
{
head = node;
node->next = nullptr;
p = node;
// p = p->next; // p 是空指针,用上面的才对
}
else
{
p->next = node;
node->next = nullptr;
p = p->next;
}
}
p->next = head;
int cnt = 0;
while(1)
{
num = k - 1;
while(num--) p = p->next;
p->next = p->next->next;
cnt++;
if(cnt == n - 1) break;
}
return p->val;
}
};