Циркулярный связанный список

Он похож на односвязный список, за исключением того, что хвостовой узел связан с головным. Обратите внимание, что в моей реализации «голова» на самом деле является хвостом, а «голова-› следующий »- на самом деле головой. Это позволяет нам быстро получить хвостовой узел, не дойдя до конца (конечно, вы также можете использовать двунаправленные ссылки, чтобы избежать проблем). Вы можете просто заменить всю «голову» на «хвост», если вам это неудобно :)

//Node definition is the same as singly linked list
//use circular linked list to solve josephus problem
template <typename Type> class LinkedList {
private:
    Node<Type> *head;
public:
    LinkedList() {
        head = NULL;
    }
~LinkedList() {
        if(head==NULL){
            return;
        }
        //head is the tail node, head->next is the head node
        Node<Type> *current_node = head->next;
        //detach to singly linked list
        head->next=NULL;
        while (current_node != NULL) {
            Node<Type> *delete_node = current_node;
            current_node = current_node->next;
            delete delete_node;
        }
    }
bool insert(Node<Type> *node, int index) {
        if (head == NULL) {
            if (index != 0) {
                return false;
            }
            head = node;
            //link to itself when only one node
            head->next=head;
            return true;
        }
        if (index == 0) {
            node->next = head->next;
            head->next = node;
            return true;
        }
        Node<Type> *current_node = head->next;
        int count = 0;
        while (current_node != head && count < index - 1) {
            current_node = current_node->next;
            count++;
        }
        if (count == index - 1) {
            node->next = current_node->next;
            current_node->next = node;
            //update tail
            if(node==head->next){
               head=node;
            }
            return true;
        }
        return false;
    }
//remove and output the m-indexed numbers
    void output_josephus(int m){
        Node<Type> *current_node=head;
        //head node may be deleted
        //set it to NULL to avoid dangling pointer
        head=NULL;
        //loop until only one node left
        while(current_node->next!=current_node){
            //count m-1: node before m-node
            for(int i=1;i<m;i++){
                current_node=current_node->next;
            }
            cout<<current_node->next->data<<" ";
            Node<Type> *delete_node=current_node->next;
            current_node->next=current_node->next->next;
            delete delete_node;
        }
        //output last node
        cout<<current_node->data<<endl;
        delete current_node;
    }
};