【算法】15.单向循环链表——解决约瑟夫环问题

目录

一、题目介绍

二、方法一：从单向循环链表的内部来处理 处理结点与结点之间的关系

三、方法二 ——从单向循环链表的外部来处理 处理就是角标之间的关系

四、完整测试代码

一、题目介绍

二、方法一：从单向循环链表的内部来处理 处理结点与结点之间的关系

1.这个方法是定义在实现类linkedSinglyCircularList里的一个方法

    //约瑟夫环问题
    public void josephusLoop() {
        if (size <= 2) {
            return;
        }
        Node p = head;
        while (size != 2) {
            p = p.next;
            Node del = p.next;
            if (del == head) {
                head = del.next;
            } else if (del == tail) {
                tail = p;
            }
            p.next = del.next;
            del.next = null;
            p = p.next;
            size--;
        }
    }

三、方法二 ——从单向循环链表的外部来处理 处理就是角标之间的关系

        int index = 0;
        while (list.size() != 2) {
            index = (index + 2) % list.size();
            list.remove(index);
        }
        System.out.println(list);

四、完整测试代码

package 练习;

import p1.接口.List;
import p3.链式结构.linkedSinglyCircularList;

public class YueSeFu {
    private static Object linkedSinglyCircularList;

    public static void main(String[] args) {
        linkedSinglyCircularList list = new linkedSinglyCircularList<>();
        for (int i = 1; i <= 41; i++) {
            list.add(i);
        }
        //从单向循环链表的内部来处理 处理结点与结点之间的关系
        //list.josephusLoop();
        //从单向循环链表的外部来处理 处理就是角标之间的关系
        
        int index = 0;
        while (list.size() != 2) {
            index = (index + 2) % list.size();
            list.remove(index);
        }
        System.out.println(list);
    }
}