单循环链表的约瑟夫环问题

约瑟夫环问题是一道经典的问题，描述如下：

有n个人围成一圈，从第k个人开始报数，报到m的人出圈，剩下的人再从1开始报数，报到m的人出圈，以此类推，直到所有人都出圈为止，求出出圈的顺序。

对于单循环链表的情况，我们可以使用链表来模拟这个过程。具体实现如下：

1. 创建一个带头结点的单循环链表，并依次将n个人节点插入链表中。

2. 从第k个人节点开始报数，每报数到第m个人节点就将该节点从链表中删除。

3. 重复执行步骤2，直到链表中只剩下一个节点为止，这个节点就是最后一个出圈的人。

代码实现如下：

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

class SingleCircularList:
    def __init__(self):
        self.head = Node(None)
        self.head.next = self.head

    def insert(self, val):
        new_node = Node(val)
        cur_node = self.head
        while cur_node.next != self.head:
            cur_node = cur_node.next
        cur_node.next = new_node
        new_node.next = self.head

    def josephus(self, k, m):
        cur_node = self.head
        for i in range(k):
            cur_node = cur_node.next

        while cur_node.next != cur_node:
            for i in range(m - 1):
                cur_node = cur_node.next
            print(cur_node.next.val, end=" ")
            cur_node.next = cur_node.next.next

        print(cur_node.val)

if __name__ == '__main__':
    n, k, m = map(int, input().split())
    lst = SingleCircularList()
    for i in range(1, n + 1):
        lst.insert(i)
    lst.josephus(k, m)

输入格式为：n k m，其中n表示链表中节点的个数，k表示从第k个节点开始报数，m表示每次报数到第m个节点。

输出为出圈的顺序。

例如，当输入为5 2 3时，输出为：3 1 5 2 4。

时间复杂度为O(nm)。