微软等数据结构与算法面试100题 第十八题
第十八题
题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始，
每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数
字）。
当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字。
分析：
这道题有很多解法，http://blog.csdn.net/v_july_v/article/details/6870251 给出了目前最快的算法。
本题目使用了链表的增删，直到剩余一个节点的时候即为最后输出的值，设表长度为n，每次删除第m个元素，则复杂度为mn。
代码：
#include<iostream>using namespace std;struct node{node * nodeNext;node * nodePrevious;int value;};int listConDelete(int length, int k){if(length<1)return -1;if(k<1)return -1;node * nodeHead, * nodeCurrent,* list;nodeCurrent = new struct node();nodeCurrent->value = 0;nodeCurrent->nodeNext = NULL;nodeCurrent->nodePrevious = NULL;nodeHead = nodeCurrent;list = nodeCurrent;for(int i = 1; i < length; i++){nodeCurrent = new struct node();nodeCurrent->value = i;list->nodeNext = nodeCurrent;nodeCurrent->nodePrevious = list;list = nodeCurrent;}nodeCurrent->nodeNext = nodeHead;nodeHead->nodePrevious = nodeCurrent;list = nodeHead;node * tempDele;while(list!=list->nodeNext){int index = 1;while(index < k){list = list->nodeNext;index++;}tempDele = list;list->nodePrevious->nodeNext = list->nodeNext;list->nodeNext->nodePrevious = list->nodePrevious;list = list->nodeNext;//cout<<tempDele->value<<" ";delete tempDele;}return list->value;}int main(){cout<<listConDelete(9,1)<<endl;cout<<listConDelete(9,0)<<endl;cout<<listConDelete(9,4)<<endl;return 0;}