_1823.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.Deque;
importjava.util.LinkedList;
importjava.util.List;

publicclass_1823 {
publicstaticclassSolution1 {
publicintfindTheWinner(intn, intk) {
List<Integer> list = newArrayList<>(n);
for (inti = 0; i < n; i++) {
list.add(i + 1);
 }
intstartIndex = 0;
while (list.size() != 1) {
intremoveIndex = (startIndex + k - 1) % list.size();
list.remove(removeIndex);
startIndex = removeIndex;
 }
returnlist.get(0);
 }
 }

publicstaticclassSolution2 {
/*
 * My completely original solution: use a double linked list to keep moving (k - 1) people from
 * the tail of the queue to the head of the queue, and then remove the kth person,
 * until there's only one person in the queue who is the winner.
 */
publicintfindTheWinner(intn, intk) {
Deque<Integer> doublyLinkedList = newLinkedList<>();
for (inti = 1; i <= n; i++) {
doublyLinkedList.addFirst(i);
 }
while (doublyLinkedList.size() > 1) {
intcounter = 1;
while (counter++ < k) {
doublyLinkedList.addFirst(doublyLinkedList.pollLast());
 }
doublyLinkedList.pollLast();
 }
returndoublyLinkedList.getLast();
 }
 }
}