public class LastMenStanding {
	
	static class LinkNode {  		
		int data;
		LinkNode next = null;
		 
		//Constructor, Time O(1), Space O(1)
		public LinkNode(int value) { 
			this.data = value;
	    }	
	
	}
	
	//Two pointers, Time O(n), Space O(n), n is input number
	public static int lastMenStanding(int n) {  
	    LinkNode head = new LinkNode(1); 
	    LinkNode prev = head; 
	    for (int i = 2; i <= n; i++) { //build circular linked list, starting from 1
	        prev.next = new LinkNode(i); 
	        prev = prev.next; 
	    } 
	    prev.next = head; //last node connects to head 
	    
	    LinkNode p = head; 
	    prev = null; 
	    int left = n; //number of nodes left in the list
	    while (left >= 2) { 
	    	if (left == 2) //second to last
	    		System.out.print("Second to last: " + prev.data); 
	        for (int i =1; i < 2; i++) {  //move every other one
	            prev = p; 
	            p = p.next; 	
	        } 	        
	        prev.next = p.next; //remove the node from the list 
	        p = prev.next;
	        left--;
	    } 
	    return p.data;
	} 
		
    public static void main(String[] args) {
    	int n = 5;
    	System.out.println( "with " + n + " men");   		
    	int p = lastMenStanding(n); 
    	System.out.println(", last: " + p);
  	
 		n = 7;
    	System.out.println( "\nwith " + n + " men");   	        	 	
    	p = lastMenStanding(n); 
    	System.out.println(", last: " + p);
	}
}