josephus

i'm close to completing the code, i'm just not sure how to go through my list and delete the mth element. Here is what I have so far, any help would greatly be appreciated.

#include <iostream>

using namespace std;

struct Node
{
int info;
Node * next;
};

void DeletNode(Node * PrevNode);
void Print(Node * first, Node * last);
void DeleteNode(Node * PrevNode);

int main()
{
int n, m;
Node * first = NULL;
Node * last = NULL;
Node * temp = NULL;
Node * temp2;
cout << "Enter Size Of List: ";
cin >> n;
cout << "Enter Interval: ";
cin >> m;
first = new Node;
first -> info = n;
first -> next = first;
last = first;

for(int i = n - 1;i > 0;i--)
{
temp = new Node;
temp -> info = i;
temp -> next = first;
first = temp;
last -> next = first;
}




Print(first,last);
return 0;
}

void Print(Node * first, Node * last)
{
Node * temp;
for(temp = first;temp != last;temp=temp->next)
{
cout << temp -> info << " -> ";
}
cout << temp -> info << endl;
}
void DeleteNode(Node * PrevNode)
{
Node * temp;
temp = PrevNode -> next;
PrevNode -> next = temp -> next;
delete temp;
}

on a side note...that code is really difficult to read...its hurting my eyes...you may pretty that up a bit.

I would use a for loop and count to m. I would start with the last node and move to the next node in each iteration.

I started at last, which seems a bit strange. I always try to think about the simpilest case first. What if m is 0? The code in the for loop will never run. That means that whatever current starts as should be the value to send to DeleteNode when m is 0. The node that is previous to the first node is the last node in your code. So, thats what I set it as.

Now, lets think about a more complicated case. When m is not 0 I need to remove a node that is m nodes after first. When m is 1 I remove first->next, which means I need to call DeleteNode(first). In hopes of generalizing things I'll use last->next instead of first. Now I'll think about when m is 2. I'll need to call DeleteNode(last->next->next). The pattern is starting to emerge, just advance the proper number of times.