双向链表实现约瑟夫
写道public class Count3Quit1 { // 数组实现 public static int count(int num) { boolean[] flags = new boolean[num]; int leftNum = flags.length; int countNum = 0; int index = 0; while (leftNum > 1) { if (!flags[index]) { countNum++; if (countNum == 3) { flags[index] = true; leftNum--; countNum = 0; } } index++; if (index == flags.length) { index = 0; } } for (int i = 0; i < flags.length; i++) { if (!flags[i]) { return i + 1; } } return -1; } // 双向链表实现 public static int countByLink(int num) { Node head = new Node(null, 1, null); Node tail = head; for (int i = 2; i <= num; i++) { Node next = new Node(tail, i, null); tail.setNext(next); tail = next; } tail.setNext(head); head.setPrevious(tail); int length = num; int countNum = 0; Node currentNode = head; while (currentNode.getData() != currentNode.getNext().getData()) { countNum++; if (countNum == 3) { currentNode.getPrevious().setNext(currentNode.getNext()); currentNode.getNext().setPrevious(currentNode.getPrevious()); countNum = 0; } currentNode = currentNode.getNext(); } return currentNode.getData(); } public static void main(String[] args) { System.out.println(countByLink(500)); } } class Node { private int data; private Node next; private Node previous; public Node getPrevious() { return previous; } public void setPrevious(Node previous) { this.previous = previous; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public Node(Node previous, int data, Node next) { super(); this.data = data; this.next = next; this.previous = previous; } } ?