环形链表的约瑟夫问题
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
- 利用链表实现
思路：（1）创建一个不带头单向循环链表，需要注意的是链表创建后返回的结点是最后一个结点，为的是链表可快速找到第一个结点和最后一个结点
（2）创建结构体指针prev和cur，分别代表最后一个结点和第一个结点，因为cur已经为第一个结点，因此count=1。遍历链表直到pcur的next还是pcur（即链表中只含有一个结点）时退出循环，循环过程中当count为m时需要将当前位置的pcur置空，count重置为1。不为count时，只需将链表往后执行即可
（3）退出循环后，返回cur->val即可
typedef struct ListNode ListNode;
ListNode* ListBuyNode(int x)
{
ListNode* node=(ListNode*)malloc(sizeof(ListNode));
if(node == NULL)
{
perror("malloc:");
exit(1);
}
node->val=x;
node->next=NULL;
return node;
}
ListNode* CreatList(int n)
{
ListNode* head=ListBuyNode(1);
ListNode* tail=head;
for(int i=2;i<=n;i++)
{
ListNode* node=ListBuyNode(i);
tail->next=node;
tail=tail->next;
}
tail->next=head;
return tail;// ！！！
}
int ysf(int n, int m )
{
ListNode* prev=CreatList(n);
ListNode* cur=prev->next;
int count=1;
while(cur->next != cur)
{
if(count == m)
{
prev->next=cur->next;
free(cur);
cur=prev->next;
count=1;
}
else
{
prev=cur;
cur=cur->next;
count++;
}
}
return cur->val;
}
- 利用循环语句实现
思路：（1）利用i，形成一个可循环遍历的类似圆形的数组
（2）利用j，来判断报的数，当报的数正好为m时，将a[i]赋值为1，并且不进行下面的循环，直到数组中仅剩一个数组的值为0
（3）退出循环，遍历数组输出值为0的数组的下标
#include<stdio.h>
int main()
{
int n = 0;
int m = 0;
scanf("%d %d",&n,&m);
int a[30] = { 0 };
int count = 0;
int i = 0;
int j = 0;
while (count < n - 1)
{
i++;
if (i>n)
i = 1;
if (a[i] == 0)
{
j++;
if (j % m == 0)
{
count++;
a[i] = 1;
j = 0;
}
}
}
for (i = 1; i < n; i++)
{
if (a[i] != 1)
{
printf("%d\n", i);
break;
}
}
return 0;
}
分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于x的节点都出现在 大于或等于x的节点之前。
你不需要保留每个分区中各节点的初始相对位置。
思路：（1）判断head是否为空，空则直接返回head
（2）创建两个两个带头单向不循环链表，一个存放小于x的值的结点，一个存放大于等于x的值的结点。lesshead和greaterhead分别为两个链表的头结点，lesstail和greatertail分别为两个链表的尾结点。
（3）创建一个pcur代替head进行链表遍历，当pcur的val小于x时将pcur存入less链表，大于等于x时将pcur存入greater链表
（4）遍历结束判断greatertail是否为空，不为空则将greatertail的next赋值为空，再将lesstail的next赋值为greatertail的next，将大小链表连接在一起
（5）创建retail赋值为lesshead的next，再将lesshead进行free置空，最后返回retail即可
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
if(head == NULL)
{
return head;
}
ListNode* lesshead=(ListNode*)malloc(sizeof(ListNode));
ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));
ListNode* lesstail=lesshead;
ListNode* greatertail=greaterhead;
ListNode* pcur=head;
while(pcur)
{
if((pcur->val) < x)
{
lesstail->next=pcur;
lesstail=lesstail->next;
pcur=pcur->next;
}
else
{
greatertail->next=pcur;
greatertail=greatertail->next;
pcur=pcur->next;
}
}
if(greatertail)
greatertail->next=NULL;
lesstail->next=greaterhead->next;
ListNode* retail=lesshead->next;
free(lesshead);
lesshead=NULL;
return retail;
}
