画个图更好理解些,偷个懒,不画了呢
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++; } } } }