约瑟夫问题(循环链表实现)

约瑟夫问题是一个经典的数学问题，也称为约瑟夫环问题。该问题的传说版本是：约瑟夫和他的朋友们（n个人）困在一个环形的监狱里，他们需要决定谁将成为自救者并得到释放。他们决定先选定一个人作为自救者，然后从此人开始，每k个人被杀死，直到只剩一个人，那个人将成为自救者。约瑟夫不想死，于是他想知道他该坐在环中哪个位置才能成为自救者。

循环链表是实现约瑟夫问题的一种常用方法。具体步骤如下：

1. 创建一个循环链表，并依次将n个人加入链表中。

2. 从链表的头节点开始遍历，每k个节点删除一个节点，直到链表中只剩下一个节点。

3. 最后剩下的那个节点就是自救者。

代码实现如下：

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def josephus(n: int, k: int) -> int:
    # 创建循环链表
    head = Node(1)
    curr = head
    for i in range(2, n + 1):
        curr.next = Node(i)
        curr = curr.next
    curr.next = head

    # 遍历链表，每k个节点删除一个节点
    curr = head
    while curr.next != curr:
        for i in range(k - 2):
            curr = curr.next
        curr.next = curr.next.next
        curr = curr.next

    # 返回最后剩下的节点的值
    return curr.val

时间复杂度为O(nk)，空间复杂度为O(1)。