python约瑟夫环扩展

约瑟夫环是一个经典的问题，它的描述如下：有 n 个人围成一圈，从第一个人开始报数，数到 m 的人出圈，然后从出圈的下一个人开始重新报数，直到剩下最后一个人。现在，我们来扩展这个问题，假设每个人有一个权值，每次出圈的人的权值会被累加到下一个出圈的人身上，直到最后只剩下一个人，求最后剩下的人的权值。

下面是一个 Python 实现：

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
 
def josephus_circle(head: Node, m: int) -> int:
    if not head or not head.next:
        return head.val
    cur = head
    while cur.next != head:
        cur = cur.next
    count = 0
    while head.next != head:
        count += 1
        if count == m:
            count = 0
            cur.next = head.next
        else:
            cur = head
        head = cur.next
    return head.val
 
def josephus_circle_extension(head: Node, m: int) -> int:
    if not head or not head.next:
        return head.val
    cur = head
    total = 0
    while cur.next != head:
        total += cur.val
        cur = cur.next
    total += cur.val
    count = 0
    while head.next != head:
        count += 1
        if count == m:
            count = 0
            cur.next = head.next
            total -= head.val
        else:
            cur = head
        head = cur.next
    return total

其中，`Node` 类表示链表节点，`josephus_circle` 函数是原始的约瑟夫环问题的解法，`josephus_circle_extension` 函数是扩展问题的解法。具体来说，`josephus_circle_extension` 函数首先遍历整个链表，计算所有人的权值之和 `total`，然后和 `josephus_circle` 函数基本一致，只是在每次出圈的时候需要将被出圈的人的权值从 `total` 中减去。最终，返回 `total` 即可。