C++循环链表实现约瑟夫环问题 |21xrx.com

C++循环链表实现约瑟夫环问题

2023-07-06 08:26:56 深夜i -- --

C++ 循环链表约瑟夫环问题实现问题解决

约瑟夫环问题是一个经典的问题，许多人在学习数据结构和算法时都会遇到它。在这个问题中，有n个人站成一个圆圈，从第k个人开始报数，报到m的那个人出列，剩下的人再从1开始报数，直到所有人都出列为止。问题是：哪些人会先出列，哪些人会后出列？

为了解决这个问题，我们可以采用循环链表来实现。循环链表是一种特殊的链表，其尾节点指向头节点，形成一个闭合的环。在循环链表中，我们可以通过指针来访问链表中的每一个节点，并且可以方便地在其中插入、删除节点。

下面是C++的实现代码：


#include <iostream>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
  int LastRemaining_Solution(int n, int m) {
    if (n <= 0 || m <= 0)
      return -1;
    
    ListNode *head = new ListNode(0);
    ListNode *cur = head;
    for (int i = 1; i <= n; i++) {
      ListNode *node = new ListNode(i);
      cur->next = node;
      cur = node;
    }
    cur->next = head->next;
    ListNode *prev = cur;
    cur = cur->next;
    while (cur->next != cur) {
      for (int i = 1; i < m; i++)
        prev = cur;
        cur = cur->next;
      
      prev->next = cur->next;
      ListNode *tmp = cur;
      cur = cur->next;
      delete tmp;
    }
    int result = cur->val;
    delete cur;
    delete head;
    return result;
  }
};
int main() {
  Solution s;
  int n, m;
  cin >> n >> m;
  cout << s.LastRemaining_Solution(n, m) << endl;
  return 0;
}

在这个代码中，我们首先创建一个长度为n的循环链表，并将其中每一个节点的值初始化为从1到n。然后我们从头节点开始遍历链表，每次走m步，直到只剩下一个节点为止。在每一轮遍历中，我们将当前节点的前一个节点和后一个节点连接起来，然后删除当前节点，将指针指向下一个节点。最后剩下的那个节点即为答案。

需要注意的是，在删除节点之前，我们需要先将指针指向下一个节点，否则会导致死循环。此外，在遍历过程中，我们需要同时记录当前节点和前一个节点，以便于删除操作。

综上所述，通过使用循环链表，我们可以方便地实现约瑟夫环问题，并且能够有效地解决该问题。

上一篇: idea打包java可执行jar包

下一篇: 如何处理C++中没有返回值的函数调用？

评论区

()

相似文章