데이터 구조 (자바 버 전) - 순환 싱글 체인 시트 로 조세 프 링 실현

조세 프 링 문제 요약: 사용자 정의 n 개인, 사용자 정의 m, m 까지 누가 나 오 는 지, 마지막 으로 남 은 하 나 는 승자 입 니 다.물론 이 문제 의 해법 과 변 체 는 매우 많 고 일부 변 체 는 이것 과 같은 사상 이다.
노드 를 삭제 할 때 머리 (head) 의 전구 지침 (rear) 을 먼저 가 져 와 야 한다 고 생각 합 니 다. 이 선행 지침 을 빌려 야 간단 하고 효과 적 인 삭 제 를 할 수 있 습 니 다. 물론 방법 도 전구 지침 법 만 이 아 닙 니 다.

package com.wrial.singlelcircleinkedlist;
/*
 * @Author  Wrial
 * @Date Created in 20:57 2019/10/9
 * @Description               
 */

public class Josephus {


    public static void main(String[] args) {
        SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList();
        singleCircleLinkedList.add(10);
        singleCircleLinkedList.showAll();
        System.out.println(singleCircleLinkedList.playByOneStep(2));
        singleCircleLinkedList.showAll();
        singleCircleLinkedList.playAll(3);

    }
}

class SingleCircleLinkedList {
    SingleCircleLinkedList() {

    }

    private Node head = null;//   

    public void add(int num) {
        if (num < 1) {
            System.out.println("         1");
            return;
        }
        Node current = null;
        for (int i = 1; i <= num; i++) {
            //            ，       current  
            if (i == 1) {
                Node node = new Node(i);
                head = node;
                current = node;
                node.next = node;
            } else {
                Node node = new Node(i);
                current.next = node;
                node.next = head;
                current = node;
            }
        }
    }

    public void showAll() {
        Node temp = head;
        if (temp == null) {
            System.out.println("      ");
            return;
        }
        while (true) {
            System.out.printf("id=%d\t", temp.getId());
            if (temp.next == head) {
                System.out.println("    ");
                break;
            }
            temp = temp.next;
        }
    }

    public int playByOneStep(int m) {
        System.out.printf("    ,      ，  %d   ",m);
        //1.   head            ，       1  ，        
        Node rear = head;
        while (true) {
            if (rear.next == head) {
                System.out.println(rear.getId());
                break;
            }
            rear = rear.next;
        }
        //2.       ，          head    

        //3.  m=1  ，     
        if (m > 1) {
            for (int i = 0; i < m - 1; i++) {
                head = head.next;
                rear = rear.next;
            }
        }
        int value = rear.next.getId();
        rear.next = rear.next.next;
        head = rear.next;
        return value;
    }

    public void playAll(int m) {

        while (true) {
            if (head.next == head){
                System.out.println("   "+head.getId());
                System.out.println("    ！");
                break;
            }
            System.out.println("  "+playByOneStep(m));
        }
    }


}


class Node {

    Node(int id) {
        this.id = id;
    }

    private int id;
    Node next;

    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                '}';
    }
}