使用单链表解决约瑟夫问题

问题描述：

N个人围成一圈，从第k个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。要求模拟此过程，输出所有出圈人的序号。

思路分析：

解算法题，关键点有两个：

1. 确定数据结构；
2. 确定算法。

那么这道题应该用什么数据结构呢？

根据题目描述，很显然我们应该使用环形链表(单链表)数据结构。

确定了数据结构，算法也就呼之欲出了。思路如下：

1. 创建一个包含N个节点的环形链表；
2. 将指针从第1个节点移动到第k个节点；
3. 以k为起始点将指针移动到第m个节点；
4. 删除第m个节点(输出m的编号)；
5. 重复第3~4步，直到链表为空。

代码实现：

1. 创建单链表节点对象：

public class LinkedNode {

    public Object element;

    public LinkedNode next;

    public LinkedNode(Object element) {
        this.element = element;
    }
}

2. 创建一个包含N个节点的环形链表：

/**
 * 创建一个包含count个节点的环形链表，并返回头节点。
 */
public LinkedNode createLinkedCircle(int count) {
    LinkedNode firstNode = new LinkedNode(0);
    LinkedNode lastNode = firstNode;
    for (int i = 1; i < count; i++) {
        LinkedNode linkedNode = new LinkedNode(i);
        lastNode.next = linkedNode;
        lastNode = linkedNode;
    }
    lastNode.next = firstNode;
    return firstNode;
}

3. 将指针移动到第k个节点

/**
 * 移动到第k个节点，即向后移动k-1个节点
 */
public LinkedNode moveToNodeK(LinkedNode firstNode, int k) {
    LinkedNode currentNode = firstNode;
    for (int i = 1; i < k; i++) {
        currentNode = currentNode.next;
    }
    LinkedNode nodeK = currentNode;
    return nodeK;
}

4. 以k为起始点，将指针移动到第m个节点

/**
 * 删除并返回nodeM
 */
public LinkedNode removeNodeM(LinkedNode startNode, int m) {
    // 因为要删除节点m，因为需要移动到节点m的前一个节点
    for (int i = 1; i < m - 1; i++) {
        startNode = startNode.next;
    }
    LinkedNode nodeM_1 = startNode;
    // 删除当前位置的元素
    LinkedNode nodeM = nodeM_1.next;
    nodeM_1.next = nodeM.next;
    return nodeM;
}

5. 重复第四步，直到集合中只有一个节点

public void repeatRemoveNodeM(LinkedNode startNode, int m) {
    while (true) {
        LinkedNode nodeM = removeNodeM(startNode, m);
        System.out.println("出列元素：" + nodeM);
        // 从nodeM的下一个节点重新报数
        startNode = nodeM.next; 
        // 链表只有一个节点时，退出循环
        if (nodeM == nodeM.next) {
            break;
        }
    }
}

总结：

本题主要考察了单链表的创建、指针移动、删除等操作。

总体的解题流程为：根据题目描述，先构建数据结构，再设计对应的算法，最后代码实现之即可。