Given a circular single linked list.Write a program that deletes every kth node until only one node is left. After kth node is deleted, start the procedure from (k+1)th node. e.g.list is 1->2->3->4->5->1 k=3 1. You are at 1, delete 3. List is: 1->2->4->5->1 2. You are at 4, delete 1 List is: 2->4->5->2 3. You are at 2,delete 5 List is: 2->4->2 4. You are at 2, delete 2 List is: 4 Return 4. How efficient you can do it?

 Solution 1: Math

Let  f(n,k) denote the position of the survivor. After the  kth person is killed, we're left with a circle of  n-1, and we start the next count with the person whose number in the original problem was (k mod n)+1. The position of the survivor in the remaining circle would be f(n-1,k), if we start counting at 1; shifting this to account for the fact that we're starting at (k mod n)+1 yields the recurrence

f(n, k) = ((f(n-1, k) + k - 1) mod n) + 1, 

f(1, k) = 1

这样理解：

新数组len = n-1， 其中1th num在原数组的位置是  (k mod n)+1, 也就是 (1 + (k-1))mod n+ 1

2nd num 在原数组位置是 （2 + （k-1））mod n + 1

3rd num 在原数组位置是 （3 + （k-1））mod n + 1

After the first person (kth from begining) is killed, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons. But the position returned by josephus(n – 1, k) will consider the position starting from k%n + 1. So, we must make adjustments to the position returned by josephus(n – 1, k).

Following is simple recursive implementation of the Josephus problem. The implementation simply follows the recursive structure mentioned above.

 

Time Complexity, O(N), DP

1 #include 
     
       2   3 int josephus(int n, int k) 4 { 5   if (n == 1) 6     return 1; 7   else 8     /* The position returned by josephus(n - 1, k) is adjusted because the 9        recursive call josephus(n - 1, k) considers the original position 10        k%n + 1 as position 1 */11     return (josephus(n - 1, k) + k-1) % n + 1;12 }13  14 // Driver Program to test above function15 int main()16 {17   int n = 14;18   int k = 2;19   printf("The chosen place is %d", josephus(n, k));20   return 0;21 }
     

 

Solution 2: Simulate the process

Singly LinkedList

先扫一遍，确定有环，并且找到head上一跳节点，然后loop直到head.next == head

1 package bloomberg; 2  3 public class Josephus { 4     public class ListNode { 5         ListNode next; 6         int val; 7         public ListNode(int val) { 8             this.val = val; 9             this.next = null;10         }11     }12     13     public int survive(ListNode head, int k) {14         if (head == null) return -1;15         ListNode prev = head;16         while (prev!=null && prev.next!=head) {17             prev = prev.next;18         }19         if (prev == null) return -1; //not a loop20         //now prev is the previous node of head21         int count = 1;22         while (head.next != head) {23             if (count == k) {24                 prev.next = head.next;25                 head = head.next;26                 count = 1;27             }28             else {29                 head = head.next;30                 prev = prev.next;31                 count++;32             }33         }34         return head.val;35     }36     37     public static void main(String[] args) {38         Josephus sol = new Josephus();39         ListNode node1 = sol.new ListNode(1);40         ListNode node2 = sol.new ListNode(2);41         ListNode node3 = sol.new ListNode(3);42         ListNode node4 = sol.new ListNode(4);43         ListNode node5 = sol.new ListNode(5);44         ListNode node6 = sol.new ListNode(6);45         node1.next = node2;46         node2.next = node3;47         node3.next = node4;48         node4.next = node5;49         node5.next = node6;50         node6.next = node1;51         int res = sol.survive(node1, 2);52         System.out.println(res);53     }54 }

 

Doubly LinkedList

可以一边loop一边确定是不是有环，while loop结束条件是 head.next != null && head.next != head, 如果出现head.next == null说明无环， 如果

head.next == head说明仅剩一个元素，正常结束