class LinkNode :  	

    #Constructor, Time O(1), Space O(1)
    def __init__(self, value):
        self.data = value
        self.next = None

#Two pointers, Time O(n), Space O(n), n is input number
def lastMenStanding(n) :
    head = LinkNode(1) 
    prev = head
    for i in range(2, n+1) :  #build circular linked list, starting from 1
        prev.next = LinkNode(i); 
        prev = prev.next; 
    prev.next = head; #last node connects to head 

    p = head
    prev = None
    left = n #number of nodes left in the list
    while left >= 2:
        if left == 2: #second to last
            print("Second to last: " + str(prev.data))
        for i in range (1 ,  2):   #move every other one
            prev = p
            p = p.next		        
        prev.next = p.next #remove the node from the list 
        p = prev.next
        left -= 1 
    return p.data

n = 5
print( "with " + str(n) + " men") 	
p = lastMenStanding(n)
print("last: " + str(p))

n = 7
print( "\nwith " + str(n) + " men")   	       	 	
p = lastMenStanding(n)
print("last: " + str(p))