7. Joseph问题

问题本身我两句话也说不明白，直接截图了。

目前公式的推导还没想明白。自己先写了一个模拟这个过程的程序，最后得到的幸存者的位置是对的。

整个过程非常简单。
就是指针每向前走两次，就把当前的那项删除。
删除后退回到上一项，继续往前走。

/**
 * Created by creat on 2018/8/4.
 */
public class JosephProblem {
    private class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * make a circle and return the last member
     */
    private ListNode createListStartFromTail(int size) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        for (int i = 1; i <= size; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        curr.next = dummy.next;
        return curr;
    }

    private void removeCurrNode(ListNode prev, ListNode curr) {
        prev.next = curr.next;
        curr.next = null;
    }

    private ListNode simulateJosephProblem(int size) { 
        int stepCount = 0;
        ListNode tail = createListStartFromTail(size);
        ListNode cur = tail;
        while (cur.val != cur.next.val) { // until there is a survivor
            ListNode prev = cur;
            cur = cur.next;
            stepCount++;
            if (stepCount % 2 == 0) {
                removeCurrNode(prev, cur);
                cur = prev; // if current node is removed, it should step back for the next iteration.
            }
        }
        return cur;
    }

    public static void main(String[] args) {
        JosephProblem jp = new JosephProblem();
        System.out.println(jp.simulateJosephProblem(40).val); //17
        System.out.println(jp.simulateJosephProblem(15).val); //15
        System.out.println(jp.simulateJosephProblem(10).val); //5
        System.out.println(jp.simulateJosephProblem(1).val);  //1
        System.out.println(jp.simulateJosephProblem(2).val);  //1
        System.out.println(jp.simulateJosephProblem(3).val);  //3
        System.out.println(jp.simulateJosephProblem(4).val);  //1
        System.out.println(jp.simulateJosephProblem(5).val);  //3
    }
}