【每日刷题】Day10

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍅

目录

1. 环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)

2. 21. 合并两个有序链表 - 力扣（LeetCode）

3. 1523. 在区间范围内统计奇数数目 - 力扣（LeetCode）

1. 环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)

//思路：根据题目所给n的大小动态开辟节点，将每个节点头尾相连，形成一个闭环（环形链表），然后返回这个环形链表最后一个开辟的节点的地址，使用两个指针——prev和pcur，pcur指针用于定位需要删除的元素，prev用于帮助pcur定位

typedef struct ListNode ListNode;

ListNode* BuyNode(int n)

{

    ListNode* pf = (ListNode*)malloc(sizeof(ListNode));//开辟节点，并设置节点内容

    if(pf==NULL)

    {

        exit(-1);

    }

    pf->val = n;

    pf->next = NULL;

    return pf;

}

ListNode* LinkList(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;//返回最后一个节点

}

 

int ysf(int n, int m )

{

    ListNode* prev = LinkList(n);//接收最后一个节点

    ListNode* pcur = prev->next;//定位第一个节点

    int count = 1;//初始pcur指向第一个节点，第一个人报数1，因此count初始为1

    while(pcur->next!=pcur)//循环条件，因为最后只会剩下一个人，因此，pcur->next会指向pcur本身

    {

        if(count==m)//如果count==m，则找到了要删除的元素

        {

            prev->next = pcur->next;//先让prev->next指向需要删除元素的下一个元素

            free(pcur);//直接删除pcur指向的元素

            pcur = prev->next;//再将pcur指向prev->next（也就是需要删除元素的下一个元素）

            count = 1;//再将count置为1

        }

        else

        {

            prev = pcur;//将pcur定位到prev的位置

            pcur = pcur->next;//然后pcur从prev的位置继续往后走

            count++;

        }

    }

    return pcur->val;

}

2. 21. 合并两个有序链表 - 力扣（LeetCode）

//思路：创建一个虚拟的新链表（不用开辟新的空间），再创建四个指针，分别是：Sentry(用于指向新链表的开头)、ptail（用于遍历新链表）、pf1（用于指向第一个链表的第一个节点）、pf2（用于指向第二个链表的第一个节点）。然后让pf1和pf2分别遍历list1和list2，比较每个节点中val值的大小，小的尾插进新链表中。

 

typedef struct ListNode ListNode;

 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)

{

    if(list1==NULL&&list2==NULL)//两个链表都为空则直接返回NULL

    {

        return NULL;

    }

    ListNode* Sentry = (ListNode*)malloc(sizeof(ListNode));//哨兵位，用于指向新链表第一个节点

    ListNode* ptail = Sentry;//用于遍历新链表

    ListNode* pf1 = list1;//指向第一个链表第一个节点

    ListNode* pf2 = list2;//指向第二个链表第一个节点

    while(pf1&&pf2)//只要有一个链表遍历完则直接退出循环

    {

        if(pf1->val<pf2->val)//小的尾插进新链表

        {

            ptail->next = pf1;

            ptail = ptail->next;

            pf1 = pf1->next;

        }

        else

        {

            ptail->next = pf2;

            ptail = ptail->next;

            pf2 = pf2->next;

        }

    }

//跳出上面循环可能是list1遍历完了，也可能是list2遍历完了，这里需要将没有遍历完的链表中的节点尾插进新链表

    while(pf1)

    {

        ptail->next = pf1;

        ptail = ptail->next;

        pf1 = pf1->next;

    }

    while(pf2)

    {

        ptail->next = pf2;

        ptail = ptail->next;

        pf2 = pf2->next;

    }

    return Sentry->next;//返回新链表的第一个节点

}

3. 1523. 在区间范围内统计奇数数目 - 力扣（LeetCode）

//最快解法，考虑到每种边界情况，计算奇数个数

int countOdds(int low, int high)

{

    int x = low%2;

    int y = high%2;

    int count = 0;

    if(x&&y)

    {

        count = (high-low)/2+1;//边界都为奇数的情况

    }

    if((x==0&&y)||(y==0&&x))

    {

        count = (high-low+1)/2;//边界一奇一偶情况

    }

    if(x==0&&y==0)

    {

        count = (high-low)/2;//边界都是偶数情况

    }

    return count;

}