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

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 
# @param n int整型 
# @param m int整型 
# @return int整型
"""
	解决思路：(1) 使用getListNode创建环形链表
			 (2) 使用get_size获取环形链表长度初始值size
			 (3) 每执行循环一次则减少size的值1
			 (4)最后当size = 1时，环形链表只剩一个节点，输出该节点的值即可
"""
class ListNode:
    def __init__(self, val) -> None:
        self.val = val
        self.next = None


class Solution:
    def LastRemaining_Solution(self, n: int, m: int) -> int:
        # write code here
        head = self.getListNode(n)
        cur = head
        pre = None
		# 获取环形链表的长度初始值
        size = self.get_size(cur)
		# 当链表长度大于1时执行循环
        while size > 1:
            count = 0
			# 使用count记录m-1步时，cur和pre的位置
            while count < m - 1:
                pre = cur
                cur = cur.next
                count += 1
			# 退出循环执行删除节点操作：将pre的next指向cur的next，
            pre.next = cur.next
			# 此时cur的值需要重新定义到删除值的下一个节点，即pre.next
            cur = pre.next
			# 环形链表伪长度-1
            size -= 1
        return cur.val

    def getListNode(self, n):
        # 创建环形链表
        head = ListNode(-1)
        cur = head
        for i in range(n):
            cur.next = ListNode(i)
            cur = cur.next
        cur.next = head.next
        return head.next

    def get_size(self, head):
		# 获取环形链表的伪长度
        lst = []
        cur = head
        while cur:
            if cur.val not in lst:
                lst.append(cur.val)
                cur = cur.next
            else:
                break
        return len(lst)