環(huán)形鏈表的約瑟夫問題

編號為 1 到 n 的 n 個人圍成一圈。從編號為 1 的人開始報數(shù)，報到 m 的人離開。
下一個人繼續(xù)從 1 開始報數(shù)。
n-1 輪結(jié)束以后，只剩下一個人，問最后留下的這個人編號是多少？

• 利用鏈表實現(xiàn)
  思路：（1）創(chuàng)建一個不帶頭單向循環(huán)鏈表，需要注意的是鏈表創(chuàng)建后返回的結(jié)點是最后一個結(jié)點，為的是鏈表可快速找到第一個結(jié)點和最后一個結(jié)點
  （2）創(chuàng)建結(jié)構(gòu)體指針prev和cur，分別代表最后一個結(jié)點和第一個結(jié)點，因為cur已經(jīng)為第一個結(jié)點，因此count=1。遍歷鏈表直到pcur的next還是pcur（即鏈表中只含有一個結(jié)點）時退出循環(huán)，循環(huán)過程中當(dāng)count為m時需要將當(dāng)前位置的pcur置空，count重置為1。不為count時，只需將鏈表往后執(zhí)行即可
  （3）退出循環(huán)后，返回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;
}

• 利用循環(huán)語句實現(xiàn)
  思路：（1）利用i，形成一個可循環(huán)遍歷的類似圓形的數(shù)組
  （2）利用j，來判斷報的數(shù)，當(dāng)報的數(shù)正好為m時，將a[i]賦值為1，并且不進(jìn)行下面的循環(huán)，直到數(shù)組中僅剩一個數(shù)組的值為0
  （3）退出循環(huán)，遍歷數(shù)組輸出值為0的數(shù)組的下標(biāo)

#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;
}

分割鏈表

給你一個鏈表的頭節(jié)點 head 和一個特定值 x ，請你對鏈表進(jìn)行分隔，使得所有小于x的節(jié)點都出現(xiàn)在 大于或等于x的節(jié)點之前。
你不需要保留每個分區(qū)中各節(jié)點的初始相對位置。

思路：（1）判斷head是否為空，空則直接返回head
（2）創(chuàng)建兩個兩個帶頭單向不循環(huán)鏈表，一個存放小于x的值的結(jié)點，一個存放大于等于x的值的結(jié)點。lesshead和greaterhead分別為兩個鏈表的頭結(jié)點，lesstail和greatertail分別為兩個鏈表的尾結(jié)點。
（3）創(chuàng)建一個pcur代替head進(jìn)行鏈表遍歷，當(dāng)pcur的val小于x時將pcur存入less鏈表，大于等于x時將pcur存入greater鏈表
（4）遍歷結(jié)束判斷greatertail是否為空，不為空則將greatertail的next賦值為空，再將lesstail的next賦值為greatertail的next，將大小鏈表連接在一起
（5）創(chuàng)建retail賦值為lesshead的next，再將lesshead進(jìn)行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;
}