您的位置:首页 > 汽车 > 时评 > 请人开发一个小程序要多少钱_手机优化大师官方免费下载_广告投放这个工作难不难做_免费外链网站seo发布

请人开发一个小程序要多少钱_手机优化大师官方免费下载_广告投放这个工作难不难做_免费外链网站seo发布

2024/12/5 22:09:38 来源:https://blog.csdn.net/qq_53706413/article/details/143574766  浏览:    关键词:请人开发一个小程序要多少钱_手机优化大师官方免费下载_广告投放这个工作难不难做_免费外链网站seo发布
请人开发一个小程序要多少钱_手机优化大师官方免费下载_广告投放这个工作难不难做_免费外链网站seo发布

主页:HABUO🍁主页:HABUO

🌜钱塘江上潮信来,今日方知我是我🌛


1.返回链表的中间结点

题目:给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

示例:

输入:head = [1,2,3,4,5]       输出:[3,4,5]       解释:链表只有一个中间结点,值为 3 。

输入:head = [1,2,3,4,5,6]    输出:[4,5,6]       解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

分析:我们要找到中间节点,是不是有两种可能性,节点数为奇数和偶数两种,奇数的话很简单就是中间的节点,偶数是不是中间就有两个节点,根据题中意思,我们需要返回的是这两个节点中的第二个节点,我们的方法是采用两个伪指针的方法,什么意思呢?就是说,两个伪指针刚开始都指向我们的头指针,走的过程中,快指针走两步,慢指针走一步,当快指针走完整个链表的时候,它们的差是不是就是整个链表的一半,这就是我们的思路,具体可看下图:

当然这里快指针走向最后的时候有些细节需要注意,奇数的话当slow走向中间节点的时候,fast刚好走向最后一个节点,也即是fast->next = NULL,奇数情况见下图,但是这个偶数情况fast就跑到链表之外,如果再进行访问就会造成对NULL访问的错误,因此处理方法见下:

fast != NULL && fast->next != NULL

综上,我们的总体代码如下:

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}

2.删除链表的倒数第 N 个结点

题目:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例:

输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]

输入:head = [1], n = 1 输出:[]

输入:head = [1,2], n = 1 输出:[1]

分析:这个题我们乍一看是不是上一个题的进阶版啊🤭,没错,这就是上一个题的通用版,会了这个题是不是,无论它让找第几个节点,我们都能找到😁。现在就让我们领略这道题的神奇,我将以两种方法去讲解,第二种方法也是第一种方法的进阶。根据上一题的思路,我们仍然采用双指针去找到倒数第n个节点,我们该怎么想呢?上一题因为它们走的步差到最后刚好一半,那这道题是不是也是这种思路呢?没错就是这种思路不过和上道题不同的是这次我们让它一开始就差距n步,那fast走到最后,因为差了n步,slow是不是就恰好在倒数第n个节点的位置,对就是这种思路🌞。因为这道题需要我们去删除,因此我们还应该需要一个伪指针指向slow前一个节点。整体思路见下:

这里需要注意虽然n=2,即是让我们去删除倒数第二个节点,但是倒数第一个和第二个之间是不是就一步,因此我们只需要让fast先走一步即可,所以总体思想见下:

struct ListNode* fast = head;
struct ListNode* slow = head;
struct ListNode* prev = NULL;
while (--n)//fast与slow相差的步数
{fast = fast->next;
}
while (fast->next != NULL)
{fast = fast->next;prev = slow;slow = slow->next;
}
prev->next = slow->next;
free(slow);
slow = NULL;
return head;

实现了上面的代码就大功告成了吗?其实这只是最正常的情况,只是我们让fast和slow动了起来,还有许多的细节没考虑到,例如:如果只有一个节点怎么办?我们要删最后一个节点怎么办?我们要删大于一个节点的头节点怎么办?好不容易有了思路,怎么还有这么多细节要考虑,是不是有点烦🫥,我劝你别烦,我们来一步一步的分析:

第一个问题:如果只有一个节点怎么办?如下所示:

如果用上面的代码两个while循环都没有进去,下面紧接着就是prev->next,立马就出现对NULL解引用的错误,还有下面 free(slow),空间还给了内存,我们的head和fast成了野指针了,是不是都是问题,所以们需要另外考虑一下这个情况,解决如下:

head = slow->next;
free(slow);
slow = NULL;
fast = NULL;
return head;

第二个问题:如果要删最后一个节点怎么办?如下所示:

这个问题只需要将我们最正常情况加上一句fast = NULL,为了防止fast成为野指针

至于第三个问题如果我们要删大于一个节点的头节点,其实在上述头节点的删除过程中已经解决,因为上述代码的妙处就在于head = slow->next在free(slow)之前,如果在它之后,是不是就要两种情况,因为slow后面又可能为NULL又可能不为NULL。因此头尾解决好,就剩下正常思路我们一开始就解决的了,所以这个问题就已经迎刃而解了,总体代码见下:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* fast = head;struct ListNode* slow = head;struct ListNode* prev = NULL;while (--n){fast = fast->next;}while (fast->next != NULL){fast = fast->next;prev = slow;slow = slow->next;}if (prev == NULL)//头删{head = slow->next;free(slow);slow = NULL;fast = NULL;return head;}else//正常删+尾删{prev->next = slow->next;free(slow);slow = NULL;fast = NULL;return head;}
}

方法二:带有哨兵位的双指针法 

分析:上面我们看到又是这种细节需要考虑,又是那种细节要考虑,是不是挺令人讨嫌😒,因此我们设置一个哨兵位节点放置在头节点处,那prev就不可能为NULL,这还考虑prev为不为NULL干什么,让它一边去!思路见下:

此时无论怎么样,prev都不可能为NULL,想怎么访问就怎么访问,上面的方法麻烦就麻烦在prev有两种可能性,但这个方法需要注意的是我们返回的是head->next,还需要注意进入循环之前把prev和head安排好,具体见下:

struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));
prev->next = head;
head = prev;
return head->next;

其它和我们上个方法正常情况是一样的。总体代码见下:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* fast = head;struct ListNode* slow = head;struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));prev->next = head;head = prev;while (--n){fast = fast->next;}while (fast->next != NULL){fast = fast->next;prev = slow;slow = slow->next;}prev->next = slow->next;free(slow);slow = NULL;return head->next;
}

🍁时间可以伸缩和折叠,唯独不能倒退🍁

🌟不要温和地走进那个良夜🌟

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com