看题目提示使用链表,就顺便复习一下单向循环链表了
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6
画个图更好理解些,偷个懒,不画了呢
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++; } } } }