当前位置：首页 > news >正文

单链表的应用（2）

news 2025/8/12 13:06:10

环形链表的约瑟夫问题

编号为 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;
}