The “Last man standing” is also called “Josephus problem”. Give a number n people standing in a circle, eliminate every kth one until the last one remain. This problem can be solved with linked list and recursion

Here we use circular linked list to solve Josephus problem. First, we build a Circular Linked List by adding n nodes. Then use a while loop to remove the kth node until only one left.

The following in the implementation of Last man standing in Java. Please note in this particular question the k is 2. We need to find the last two men alive in stead of last man.

**Amazon Interview Question (CareerCup):**

Last Man Standing: A king gathers all the men in the kingdom who are to be put to death for their crimes, but because of his mercy, he will pardon one. He gathers the men into a circle and gives the sword to one man. The man kills the man to his left, and gives the sword to the man to the dead man’s left. The last man alive is pardoned.

With 5 men, the 3rd is the last man alive.

Write a program that accepts a single parameter: a number N that represents the number of criminals to start with. The program should output the number of the last two men alive.

Example #1: myProgram 5

would output:

5, 3

Example #2: myProgram 7

would output:

3, 7

** Java Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
class LinkedNode { protected int data; protected LinkedNode next = null; //Default constructor public LinkedNode() {} //Constructor, Time O(1), Space O(1) public LinkedNode(int val) { this.data = val; } //Constructor, Time O(1), Space O(1) public LinkedNode(int val, LinkedNode node) { this.data = val; this.next = node; } //Override, Time O(1), Space O(1) public String toString() { return String.valueOf(data); } } public class LastMenStanding { //Delete in circular linked list, Two pointers, //Time O(2*n) ~ O(n), Space O(n), n is number of nodes in list public static int lastStanding(int n) { LinkedNode head = new LinkedNode(1); LinkedNode prev = head; for (int i = 2; i <= n; i++) { //build circular linked list prev.next = new LinkedNode(i); prev = prev.next; } prev.next = head; LinkedNode p1 = head, p2 = head; int left = n; while (p1.next != p1) { if (left == 2) //second to last System.out.print("Second to last: " + p2.data); int count = 1; while (count != 2) { //every other one p2 = p1; p1 = p1.next; count++; } p2.next = p1.next; p1 = p2.next; left--; } return p1.data; } public static void main(String[] args) { //Test case 1, N=5 int n = 5; System.out.println( "With " + n + " men, the last two standing are: "); int p = lastStanding(n); System.out.println(", last: " + p); System.out.println(); //Test case 2, N=7 n = 7; System.out.println( "With " + n + " men, the last two standing are: "); p = lastStanding(n); System.out.println(", last: " + p); } } |

**Output:**

With 5 men, the last two standing are:

Second to last: 5, last: 3

With 7 men, the last two standing are:

Second to last: 3, last: 7

**O Notation:**

Time complexity: O(n)

Space complexity: O(n)

Download LastMenStanding.java

Java Coding Interview Pocket Book (2nd Edition)

Josephus problem solution using recursion