题解 | #孩子们的游戏(圆圈中最后剩下的数)#

class LinkList:
    """
    定义链表
    """
    def __init__(self, x, linknode=None):
        super(LinkList, self).__init__()
        self.val = x
        self.next = linknode

class Solution:
    @staticmethod
    def create_link(values):
        """
        创建环形链表，环是通过这句话加上的【temp.next = pHead.next】
        """
        pHead = LinkList(0)
        temp = pHead
        for ele in values:
            temp.next = LinkList(ele)
            temp = temp.next
        temp.next = pHead.next
        return pHead.next
    
    def LastRemaining_Solution(self, n, m):
        # write code 
        if n == 0&nbs***bsp;m == 0:
            return -1
        phead = self.create_link(list(range(n)))
        cur = phead
        count = 0
        while True:
            pre = cur
            cur = cur.next
            count += 1
            # 执行删除倒霉蛋小孩的操作
            if count == m-1:
                count = 0
                pre.next = cur.next
                cur = pre.next
            if pre == cur:
                break
        return pre.val

递推公式不好理解，换一种方法：使用环形链表来模拟这个过程，即复习了环形链表也通俗易懂，人畜无害，下面上代码