Josephus Circle implementation using STL list | structure for a node in circular linked list ; Function to find the only person left after one in every m - th node is killed in a circle of n nodes ; Create a circular linked list of size N . ; Connect last node to first ; while only one node is left in the linked list ; Find m - th node ; Remove the m - th node ; Driver program to test above functions
class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def getJosephusPosition ( m , n ) : NEW_LINE INDENT head = Node ( 1 ) NEW_LINE prev = head NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT prev . next = Node ( i ) NEW_LINE prev = prev . next NEW_LINE prev . next = head NEW_LINE DEDENT ptr1 = head NEW_LINE ptr2 = head NEW_LINE while ( ptr1 . next != ptr1 ) : NEW_LINE INDENT count = 1 NEW_LINE while ( count != m ) : NEW_LINE INDENT ptr2 = ptr1 NEW_LINE ptr1 = ptr1 . next NEW_LINE count += 1 NEW_LINE DEDENT ptr2 . next = ptr1 . next NEW_LINE ptr1 = ptr2 . next NEW_LINE DEDENT print ( " Last ▁ person ▁ left ▁ standing ▁ ( Josephus ▁ Position ) ▁ is ▁ " , ptr1 . data ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 14 NEW_LINE m = 2 NEW_LINE getJosephusPosition ( m , n ) NEW_LINE DEDENT