题目一
快速找到未知长度的单链表的中间节点
普通方法
由于单链表不知道长度，必须遍历完整个单链表才知道单恋表的长度，然后根据一般的长度去找中间结点，这是普通方法。
问的是快速找到，当然要用快速的方法啦
有一个很巧妙的方法，快慢指针
快指针每次走2个结点，慢指针每次走1个结点，当快指针走完链表，慢指针刚好走到中间，这就是快慢指针的核心思想。
int GetMidNode(node* L) //寻找链表中间值
{
int a;
node *search,*mid;
mid = search = L;
while(search->next != NULL)
{
if(search->next->next != NULL)
{
search = search->next->next;
mid= mid->next;
}
else
{
search = search->next;
}
}
a = mid->data;
return a;
}
题目二
约瑟夫环
问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）
循环单链表解法：
#include<stdio.h>
#include <stdlib.h>
typedef struct node//节点存放一个数据和指向下一个节点的指针
{
int data;
struct node* pnext;
} Node;
Node *link_create(int n)//创建n个节点的循环链表
{
//先创建第1个节点
Node *p,*q,*head;
int i ;
p = (Node *)malloc(sizeof(Node));
head = p;
p->data = 1;
for(i = 2;i<=n;i++)//再创建剩余节点
{
q = (Node *)malloc(sizeof(Node));
q->data = i;
p->pnext = q;
p = q;
}
p->pnext = head;//最后一个节点指向头部，形成循环链表
return head;
}
void link_process(Node *head,int k,int m)//从编号为k(1<=k<=n)的人开始报数，数到m的那个人出列；
{
int i;
Node *p = head,*tmp1;
while(p->data != k)//p指向的节点data为k
{
tmp1 = p;
p = p->pnext;
}
while(p->pnext != p)
{
for(i=1;i<m;i++)
{
tmp1 = p;
p = p->pnext;
}
printf("%d ",p->data);
tmp1->pnext= p->pnext;
free(p);
p = tmp1->pnext;
}
printf("%d ",p->data);
free(p);
}
int main()
{
Node *head = link_create(5);
link_process(head,3,1);
system("pause");
return 0;
}
C++数列推导实现（数学推导式）
推导求解
现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n >= k。幸存者的位置为 pn 。
显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 pn-1 。如果能够找到从 pn-1 到 pn 的递推关系，那么问题就解决了。
重新排序之后，每个人的位置发生了下面这些变化：
- 1 -> n-k+1
- 2 -> n-k+2
- ...
- k-1 -> n-1
- k 被杀死
- k+1 -> 1
- ...
- pn -> pn-1
- ...
- n-1 -> n-k+1
- n -> n-k
很容易我们能得到这样一个关系式：pn = (pn-1 + k) % n 。再加上刚才讨论的特例，只有一个人的情况时，p1 = 1 。递推式就已经很明显了。
当然上文只讨论了 n>=k 的情形，实际上对于 n<k 的情形，刚才所得到的递推式依然适用，我们就不展开讨论了。
#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::cin;
using std::list;
int main()
{
int total = 0;
cout << "Please input total number of people : ";
cin >> total;
int number = 0;
cout << "Please input selected number : ";
cin >> number;
/* If number = 3
* f(1) = 0
* f(2) = 1 = (f(1) + 3) % 2
* f(3) = 1 = (f(2) + 3) % 3
* f(4) = 0 = (f(3) + 3) % 4
* f(5) = 3 = (f(4) + 3) % 5
* ...
* f(n) = x = (f(n-1) + 3) % n
* */
int last = 0; // f(1) = 0
for(int i = 2; i <= total; ++i)
{
last = (last + number) % i;
}
cout << "The last one is : " << last + 1 << endl;
return 0;
}
