单向链表实现
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n <= 0) return -1;
m -= 1;
SingleCircleLinkedList1 list = new SingleCircleLinkedList1();
for (int i = 0; i < n; i++) {
list.add(i);
}
list.reset();
while (list.size() != 1) {
for (int i = 0; i < m; i++) {
list.next();
}
list.remove(); // 每次只删掉一个人
}
return list.get(0);
}// public static void main(String[] args) {
//
// Solution solution = new Solution();
//
// int i = solution.LastRemaining_Solution(5, 3);
//
// System.out.println(i);
//
// }
}
class SingleCircleLinkedList1 {
private int size;
private Node first;
private Node current;
private static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
public int size() {
return size;
}
public int get(int index) {
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.val;
}
public void add(int val) {
if (size == 0) {
first = new Node(val, null);
first.next = first;
} else {
Node prev = first;
for (int i = 0; i < size - 1; i++) {
prev = prev.next;
}
prev.next = new Node(val, prev.next);
}
size++;
}
private int remove(Node node) {
if (node == first) {
if (size == 1) {
first = null;
} else {
Node last = first;
for (int i = 0; i < size - 1; i++) {
last = last.next;
}
first = first.next;
last.next = first;
}
} else {
Node prev = first;
while (prev.next != node) {
prev = prev.next;
}
prev.next = node.next;
}
size--;
return node.val;
}
public void reset() {
current = first;
}
public int next() {
if (current == null) return -1;
current = current.next;
return current.val;
}
public int remove() {
if (current == null) return -1;
int val = this.remove(current);
if (size == 0) {
current = null;
} else {
current = current.next;
}
return val;
}}
