4.链表部分练习题

1.约瑟夫问题

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

本题可使用循环链表解决
设置一个节点firsthead指向被删除节点
一个helper节点指向被删除节点的前一个节点
在下列代码中
在构建循环链表时，firsthead.next=第一个节点
在游戏开始时，需要使得firsthead=第一个节点

package com.zhiyang.linkedlist;

public class Josepfu {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.addBoy(5);
        // circleLinkedList.showList();
        circleLinkedList.countBoy(1, 2, 5);

    }

}

class CircleLinkedList {
    private Boy firsthead = null;

    public void addBoy(int n) {
        firsthead = new Boy(-1);
        if (n < 1) {
            System.out.println("人数过少");
            return;
        }
        Boy curBoy = firsthead;
        for (int i = 1; i <= n; i++) {
            Boy boy = new Boy(i);
            curBoy.next = boy;
            boy.next = firsthead.next;
            curBoy = curBoy.next;
        }
    }

    // 遍历环形链表
    public void showList() {
        if (firsthead == null) {
            return;

        }

        Boy curBoy = firsthead.next;
        while (true) {
            System.out.printf("小孩的编号%d\n", curBoy.getNo());
            if (curBoy.next == firsthead.next) {
                break;
            }
            curBoy = curBoy.next;
        }

    }

    // 根据用户输入，计算小孩出圈顺序
    /**
     * 
     * <p>
     * Title: countBoy
     * </p>
     * <p>
     * Description:
     * </p>
     * void
     * 
     * @param startno  从第几个小孩开始
     * @param countNum 数几个出圈
     * @param nums     总共多少人
     */
    public void countBoy(int startno, int countNum, int nums) {
        if (firsthead == null || startno < 1 || startno > nums) {
            System.out.println("参数错误");
            return;
        }

        // 创建一个辅助指针，帮助完成小孩出圈
        Boy helperBoy = firsthead.next;
        while (true) {
            if (helperBoy.next == firsthead.next) {
                break;
            }
            helperBoy = helperBoy.next;
        }
        // 现在helperBoy=队列最后一个
        // 出圈前，需要先移动到statrno位置来
        System.out.printf("目前helper指向的节点是%d\n", helperBoy.getNo());
        System.out.printf("目前firsthead指向的节点是%d\n", firsthead.getNo());
        firsthead = firsthead.next;
        for (int j = 0; j < startno - 1; j++) {
            firsthead = firsthead.next;
            helperBoy = helperBoy.next;
        }
        System.out.printf("目前helper指向的节点是%d\n", helperBoy.getNo());
        System.out.printf("目前firsthead指向的节点是%d\n", firsthead.getNo());
        while (true) {
            if (helperBoy == firsthead) {
                break;
            }
            for (int j = 0; j < countNum - 1; j++) {
                firsthead = firsthead.next;
                helperBoy = helperBoy.next;
            }
            // 这是first指向的小孩就是要出圈的小孩
            System.out.printf("小孩%d出圈\n", firsthead.getNo());
            firsthead = firsthead.next;
            helperBoy.next = firsthead;
        }
        System.out.printf("最后留在圈中的小孩的节点%d", firsthead.getNo());
    }
}

class Boy {
    private int no;
    public Boy next;

    public Boy(int no) {
        super();
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

}

目前helper指向的节点是5
目前firsthead指向的节点是-1
目前helper指向的节点是5
目前firsthead指向的节点是1
小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最后留在圈中的小孩的节点3