循环单链表约瑟夫环python

以下是循环单链表约瑟夫环的 Python 实现：

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def remove(self, node):
        if self.head == node:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = self.head.next
            self.head = self.head.next
        else:
            current = self.head
            while current.next != self.head:
                if current.next == node:
                    current.next = node.next
                    break
                current = current.next

    def __len__(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
            if current == self.head:
                break
        return count

def josephus(circle, step):
    current = circle.head
    while len(circle) > 1:
        for i in range(step - 1):
            current = current.next
        circle.remove(current)
        current = current.next
    return circle.head.data

# 示例
circle = CircularLinkedList()
circle.append(1)
circle.append(2)
circle.append(3)
circle.append(4)
circle.append(5)

print(josephus(circle, 2)) # 输出 3

在此示例中，我们首先定义了一个 `Node` 类和一个循环单链表 `CircularLinkedList` 类。`Node` 类用于表示链表中的一个节点，而 `CircularLinkedList` 类则用于表示整个循环单链表。在 `CircularLinkedList` 类中，我们实现了 `append` 方法用于向链表中添加节点，`remove` 方法用于从链表中删除节点，以及 `__len__` 方法用于获取链表中节点的数量。

接着，我们定义了一个 `josephus` 函数来模拟约瑟夫环。该函数接受两个参数：一个循环单链表 `circle` 和一个步长 `step`。在函数中，我们首先将当前节点指向链表的头节点。然后，我们进入一个循环，直到链表中只剩下一个节点为止。在每次循环中，我们先将当前节点向前移动 `step - 1` 步，然后将当前节点所指向的节点从链表中删除。最后，我们将当前节点指向下一个节点，并继续进行下一轮循环。

最后，我们在示例中创建了一个循环单链表，然后调用 `josephus` 函数来模拟约瑟夫环。在此示例中，我们设定步长为 2，因此最终输出的结果应该是第三个节点的值，即 3。