单向链表实现

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;
}

}