The Josephus Problem People are standing in a circle (Links to an external site.)Links to an external site. waiting to

#include <bits/stdc++.h>
using namespace std;

/* structure for a Node */
struct Node {
    int data;
    Node* next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

/*Utility function to print the circular linked list*/
void printList(Node* head)
{

    if (head == NULL)
        return;
    Node* temp = head;
    do {
        cout << temp->data << "->";
        temp = temp->next;
    } while (temp != head);
    cout << head->data << endl;
}

/*Function to delete every kth Node*/
void deleteK(Node** head_ref, int k)
{
    Node* head = *head_ref;

    // If list is empty, simply return.
    if (head == NULL)
        return;

    // take two pointers - current and previous
    Node *curr = head, *prev;
    while (true) {

        // Check if Node is the only Node\
        // If yes, we reached the goal, therefore
        // return.
        if (curr->next == head && curr == head)
            break;

        // Print intermediate list.
        printList(head);

        // If more than one Node present in the list,
        // Make previous pointer point to current
        // Iterate current pointer k times,
        // i.e. current Node is to be deleted.
        for (int i = 0; i < k; i++) {
            prev = curr;
            curr = curr->next;
        }

        // If Node to be deleted is head
        if (curr == head) {
            prev = head;
            while (prev->next != head)
                prev = prev->next;
            head = curr->next;
            prev->next = head;
            *head_ref = head;
            free(curr);
        }

        // If Node to be deleted is last Node.
        else if (curr->next == head) {
            prev->next = head;
            free(curr);
        }
        else {
            prev->next = curr->next;
            free(curr);
        }
    }
}

/* Function to insert a Node at the end of
a Circular linked list */
void insertNode(Node** head_ref, int x)
{
    // Create a new Node
    Node* head = *head_ref;
    Node* temp = new Node(x);

    // if the list is empty, make the new Node head
    // Also, it will point to itself.
    if (head == NULL) {
        temp->next = temp;
        *head_ref = temp;
    }

    // traverse the list to reach the last Node
    // and insert the Node
    else {
        Node* temp1 = head;
        while (temp1->next != head)
            temp1 = temp1->next;
        temp1->next = temp;
        temp->next = head;
    }
}

/* Driver program to test above functions */
int main()
{
    int i;
    // insert Nodes in the circular linked list
    struct Node* head = NULL;
    for(i=1;i<=41;i++)
    {
   insertNode(&head, i);
    }

    int k = 2;

    // Delete every kth Node from the
    // circular linked list.
    deleteK(&head, k);

    return 0;
}