画个图更好理解些,偷个懒,不画了呢
class Node{
int val;
Node next = null;
public Node(int val) {
this.val = val;
}
}
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n<=0||m<=0)return -1;
//1.将数字串起来,围成一个圈
Node head = new Node(0);
Node headP1 = head;
for(int i=1;i<n;i++){
headP1.next = new Node(i);
headP1 = headP1.next;
}
headP1.next = head;
//定义一个新的头节点开始数数
Node headP2 = head;
Node pre = null ;//前驱节点
int count = 1;//记录当前走过的节点个数
while(true){
if(count==m){//当走过的个数为m个时开始删除当前节点,然后重新循环
if(headP2.next == pre) return pre.val;//结束条件是:链表中只剩下两个节点
//下面是删除节点过程
Node temp = headP2.next;
pre.next = temp;
headP2.next = null;
headP2 = temp;
//从头重新计数
count=1;
}else{
pre = headP2;
headP2 = headP2.next;
count++;
}
}
}
}


京公网安备 11010502036488号