剑指 小朋友圆圈

通过环形链表模拟，解决这道题，时间复杂度O(mn),如果m,n太大，时间太长。

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        result=head=ListNode(0)
        i=0
        if n==0 or m==0:
            return -1
        while i<n:
            node=ListNode(i)
            head.next=node
            head=head.next
            i+=1
        head.next=result.next
        print(result)
        count=1
        p=result.next
        pre=ListNode(-1)
        while pre.val!=p.val:
            while count<m:
                pre=p
                p=p.next
                count+=1
            pre.next=p.next
            p=pre.next
            count=1
        return p.val if p.val else -1

约瑟夫环问题, 当只有一个元素的时候，输出的元素是0，一直往上回溯的话，把当前0的坐标映射过去就可以得到结果。那么n-1轮的结果映射到n轮，需要(f(n-1)+m)%第n轮的数组长度。

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/

# -*- coding:utf-8 -*-
class Solution:

    def LastRemaining_Solution(self, n, m):
        # write code here

#         if n<=0 or m<=0:
#             return -1
#         x=0

#         for i in range(2,n+1):
#             x=(x+m)%i

#         return x
          if n<=0 or m<=0:return -1
          if n==1:return 0
          return ((self.LastRemaining_Solution(n-1,m)+m)%n)%(1e7+9)