环形链表的约瑟夫问题_牛客题霸_牛客网
经典的约瑟夫环
#include <stdint.h>
#include <stdlib.h>
//创建链表
typedef struct ListNode ListNode;
ListNode* buyNode(int x){
ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
if(newNode==NULL){
exit(1);
}
newNode->val=x;
newNode->next=NULL;
return newNode;
}
//创建新节点
ListNode* createList(int n){
ListNode* phead=buyNode(1);
ListNode* ptail=phead;
for(int i=2;i<=n;i++)
{
ptail->next=buyNode(i);
ptail=ptail->next;
}
ptail->next=phead;
return ptail;//返回ptail,因为需要有前一个指针和后一个指针
}
int ysf(int n, int m ) {
// write code here
ListNode* prev=createList(n);
ListNode* pcur=prev->next;
int count=1;
while(pcur->next!=pcur){
if(count==m){
prev->next=pcur->next;//先让prev指向pcur的next要不然会找不到pcur
free(pcur);
pcur=prev->next;
count=1;//置为1重新计数
}
else{
prev=pcur;
pcur=pcur->next;
count++;
}
}
return pcur->val;
}. - 力扣（LeetCode）
反转链表
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
return NULL;
}
struct ListNode* n1;
struct ListNode* n2;
struct ListNode* n3;
n1=NULL;
n2=head;
n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
. - 力扣（LeetCode）
链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode*slow,*fast;;
slow=fast=head;
while(fast && fast->next)//不能写成while(fast->next && fast)
因为while会先判断前面的条件，而fast很可能直接就跑到空了，根本没有next属性导致报错
也就是短路性质
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
. - 力扣（LeetCode）
回文链表
核心思想：将链表反转后，比较后半部分是否相同
遍历链表找到中间节点，从中间节点为分割线去比较两边是否先相同
typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head){
ListNode* n1=NULL;
ListNode* n2=head;
ListNode* n3=head->next;
while(n2){
n2->next=n1;
n1=n2;
n2=n3;
if(n3){
n3=n3->next;
}
}
return n1;
}
bool isPalindrome(struct ListNode* head){
if(head==NULL||head->next==NULL)
{
return true;
}
ListNode* fast=head;
ListNode* slow=head;
//遍历得到中间节点
while(fast->next&&fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
//右半部分反转后与前半部分比较
ListNode* right=reverseList(slow->next);
ListNode* cur=head;
while(right){
if(right->val!=cur->val){
return false;
}
else{
right=right->next;
cur=cur->next;
}
}
return true;
}. - 力扣（LeetCode）
合并两个有序链表
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if(list1==NULL)//如果list1为空，返回list2
{
return list2;
}
if(list2==NULL)
{
return list1;
}
ListNode*head,*tail;
head=tail=(ListNode*)malloc(sizeof(ListNode));
while(list1&&list2)//判断循环条件，有一个为空就跳出循环
{
if(list1->val<list2->val)//l1<l2的值
{
tail->next=list1;//把list1链接到tail后面
tail=tail->next;//tail迭代往后走
list1=list1->next;//list1迭代往后走
}
else{
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
if(list1)
{
tail->next=list1;
}
if(list2)
{
tail->next=list2;
}
ListNode* ret=head->next;
free(head);
head=NULL;//动态申请的空间需要手动释放
return ret;
}
. - 力扣（LeetCode）
分割链表
给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。
思路：创建两个新链表，一个放比特定值小的数，一个放大的然后链接起来；
注意事项：对于大链表中的尾节点，需要置空，要不会出现死循环；创建哨兵位，需要手动释放空间；让小链表的尾指向大链表哨兵位的next
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
//开两个哨兵位，虚拟节点,方便尾插
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
lesstail->next=NULL;
greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
greatertail->next=NULL;
struct ListNode*cur=head;
while(cur)
{
if(cur->val<x)
{
lesstail->next=cur;
lesstail=cur;
}
else
{
greatertail->next=cur;
greatertail=cur;
}
cur=cur->next;
}
lesstail->next=greaterhead->next;
greatertail->next=NULL;
struct ListNode* newhead=lesshead->next;
free(lesshead);
free(greaterhead);
return newhead;
}
