循环链表约瑟夫环c++实现

循环链表约瑟夫环是一个经典的问题，下面是一个实现：

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


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

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

    def remove(self, node):
        if self.head == node:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
                self.tail.next = self.head
        else:
            prev_node = self.head
            while prev_node.next != node:
                prev_node = prev_node.next
            prev_node.next = node.next
            if self.tail == node:
                self.tail = prev_node

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

    def __iter__(self):
        curr_node = self.head
        while curr_node:
            yield curr_node
            curr_node = curr_node.next
            if curr_node == self.head:
                break


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


if __name__ == '__main__':
    c = CircularLinkedList()
    for i in range(1, 11):
        c.append(i)
    print(josephus(c, 3))  # 输出 4

这个实现中，我们首先实现了一个循环链表的类 `CircularLinkedList`，它包含了 `append` 和 `remove` 方法，分别用于添加和删除节点。在 `__len__` 和 `__iter__` 方法中，我们实现了对链表长度和遍历的支持。

在 `josephus` 函数中，我们首先将当前节点 `curr_node` 初始化为链表头节点，然后每次循环，我们将 `curr_node` 向前移动 `step - 1` 步，找到下一个要删除的节点 `next_node`，然后通过 `circle.remove` 方法将当前节点 `curr_node` 从链表中删除。最后，我们将 `curr_node` 更新为 `next_node`，继续循环，直到链表中只剩下一个节点为止。

在主函数中，我们创建了一个含有 10 个节点的循环链表，然后调用 `josephus` 函数，传入循环链表和步长 3，输出结果为 4，符合预期。