约瑟夫问题 用循环链表算法 时间 复杂度多少# JobHunting - 待字闺中
f*e
1 楼
class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
class Solution{
public int live(int n, int k){
ListNode head = new ListNode(1);
ListNode node = head;
for(int i = 2; i <= n; i++){
node.next = new ListNode(i);
node = node.next;
}
node.next = head;
System.out.println("before remove");
printList(head);
System.out.println("removing the nodes");
while(head.next != head){
int count = 1;
while(count < k - 1){
head = head.next;
count++;
}
System.out.print(head.next.val + "->");
head.next = head.next.next;
head = head.next;
}
System.out.println();
System.out.println("after remove");
return head.val;
}
public void printList(ListNode head){
if (head != null){
ListNode temp = head;
do{
System.out.print(temp.val + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args){
Solution s = new Solution();
int n = 5;
int k = 2;
System.out.println(s.live(n, k));
int n1 = 7;
int k1 = 3;
System.out.println(s.live(n1, k1));
int n2 = 14;
int k2 = 2;
System.out.println(s.live(n2, k2));
}
}
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
class Solution{
public int live(int n, int k){
ListNode head = new ListNode(1);
ListNode node = head;
for(int i = 2; i <= n; i++){
node.next = new ListNode(i);
node = node.next;
}
node.next = head;
System.out.println("before remove");
printList(head);
System.out.println("removing the nodes");
while(head.next != head){
int count = 1;
while(count < k - 1){
head = head.next;
count++;
}
System.out.print(head.next.val + "->");
head.next = head.next.next;
head = head.next;
}
System.out.println();
System.out.println("after remove");
return head.val;
}
public void printList(ListNode head){
if (head != null){
ListNode temp = head;
do{
System.out.print(temp.val + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args){
Solution s = new Solution();
int n = 5;
int k = 2;
System.out.println(s.live(n, k));
int n1 = 7;
int k1 = 3;
System.out.println(s.live(n1, k1));
int n2 = 14;
int k2 = 2;
System.out.println(s.live(n2, k2));
}
}