您的位置:首页 > 游戏 > 手游 > 今天三河燕郊确诊名单_商业网站建设_百度广告联盟一个月能赚多少_飓风seo刷排名软件

今天三河燕郊确诊名单_商业网站建设_百度广告联盟一个月能赚多少_飓风seo刷排名软件

2024/12/23 5:42:10 来源:https://blog.csdn.net/qq_53706413/article/details/144041745  浏览:    关键词:今天三河燕郊确诊名单_商业网站建设_百度广告联盟一个月能赚多少_飓风seo刷排名软件
今天三河燕郊确诊名单_商业网站建设_百度广告联盟一个月能赚多少_飓风seo刷排名软件

主页:HABUO🍁主页:HABUO

🍁如果再也不能见到你,祝你早安,午安,晚安🍁


1.复杂链表的复制

题目:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2:

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

输出:[[1,1],[2,1]]

分析:这是一个比较复杂的题目,我们只有见的多了之后我们可能看到这样新的题目,才会有敲门砖,又时候差的就是刚开始的敲门砖,敲门砖有了,剩下的就是用我们之前拥有的思想去实现就完了。因此呢,在这里我直接给出这个思路,以后再遇到这样类型的我们是不是就会了啊。首先,我们直接遍历是不是没办法搞啊,因为你random不知道指向谁,有些人可能会说,那我直接访问该节点的random不就行了,是的,但是如果我们链表当中,有两个相同值的节点怎么办?因为我们复制节点是复制它们的值和指向,地址是不是同等的复制下来,假如两个3,你只知道random指向3的那个节点,但是具体哪个节点我们是不是无能为力啊。因此这种直接的方法难以实现。好了,接下来很重要,1.我们为每一个节点备份一个节点,而且呢,让这个节点的next指向这个备份节点,让备份节点的next指向原链表该节点的next。2.让每一个备份节点的random指向它应该指向的备份节点,有人会问,那这咋指向,好关键点来了,你发现没有,备份节点的random是不是就是原节点的random的next啊,对不对,这就是这个题的关键。3.恢复原链表,让新链表链接起来,并返回头指针。这就是我们整体的思路。下面进行一步一步实现。

第一步:为每个节点进行备份,并且让这个节点的next指向这个备份节点,让备份节点的next指向原链表该节点的next,由于random画上之后错综复杂,不再指出,本题以示例1为导向。如下图所示:

代码实现如下:

//1.为每个链表节点备份一个节点Node* cur = head;while(cur){Node* copyNode = (Node*)malloc(sizeof(Node));copyNode->val = cur->val;copyNode->next = cur->next;cur->next = copyNode;cur = copyNode->next;}

第二步 让每一个备份节点的random指向它应该指向的备份节点,我们以13节点为例,看下图就会明白。因为每一个节点的备份节点是不是就是原节点的next因此我们想要备份节点指向它所指向的random,找到原节点的random是不是就行了啊。

代码实现如下:

//2.为备份节点的random进行链接cur = head;while(cur){//cur->random有可能指向NULLif(cur->random == NULL){cur->next->random = NULL;cur = cur->next->next;continue;}//每个备份节点的random,都是原节点的random的备份节点cur->next->random = cur->random->next;cur = cur->next->next;}

第三步,我们破坏了原链表的链接是不是需要恢复,而且新链表也还没有连接上,下面是不是就是恢复和链接,这里就只需要多设置几个指针来回的走就ok,前面的几道题的铺垫,相信这对于我们来说应该相对很简单。

//恢复原链表,把备份链表进行链接cur = head;Node* newHead = cur->next;Node* copyCur = newHead;Node* curNext = newHead->next;while(cur){cur->next = curNext;if(curNext == NULL){copyCur->next = NULL;break;}copyCur->next = curNext->next;copyCur = copyCur->next;cur = curNext;curNext = curNext->next->next;}return newHead;

要注意curNext是不是到最后就为NULL了,但是我们下面还有要访问它的next的代码,因此需要在这之前做一个判断语句做一个判断,防止错误。需要注意我们这种方法是不是对原链表进行修改了,这种操作是不太好的,等到好面我们学习的深入会用更优的方法去解决。

2.对链表进行插入排序

题目:给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

  1. 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  3. 重复直到所有输入数据插入完为止。

示例1:

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

示例2:

输入: head = [-1,5,3,4,0]              输出: [-1,0,3,4,5]

分析:我们可能直接的想法就是从第一个数据起,拿到一个数据就从头遍历放到合适的位置直至最后一个节点。 但是这是链表啊,这样操作是不是代价也太高了,要是数组你发到一个合适的位置,只需要将后面的数据往后移动即可,链表不太行。所以,我们的思路是,将第一个节点当作一个新链表的起始节点,之后从后面链表当中每次取一个节点,往新链表当中进行逐一比较进行插入,当然有可能头插,也有可能尾插,也可能中间插入,所以分三种情况,这就是我们的大致思想,具体如下图所示:

所以分三种情况进行插入,头插实现如下:注意我们一开始让head指向了head->next,因为我们让第一个节点当作新链表的头了

//头插if(cur->val >= head->val){head->next = cur;cur = head;newHead = cur;head =headNext;if(headNext == NULL)break;headNext = headNext->next;continue;}

中间插入实现代码如下:

while(cur){//中间插入if(cur->val < head->val){curPrev = cur;cur = cur->next;}else{head->next = cur;curPrev->next = head;head = headNext;if(headNext == NULL)break;headNext = headNext->next;break;}}

尾插的话是不是就是中间插入情况的cur指向了NULL还没找到合适的位置,因此实现代码如下:

//尾插if(cur == NULL){curPrev->next = head;head->next = NULL;head = headNext;if(headNext == NULL)break;headNext = headNext->next;}

所以将这些代码串起来放到一个循环当中是不是就实现了,因此完整代码如下:

 typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head) {if(head == NULL || head->next == NULL)return head;Node* newHead = head;head = head->next;newHead->next = NULL;Node* headNext = head->next;while(head) {Node* cur = newHead;Node* curPrev = NULL;//头插if(cur->val >= head->val){head->next = cur;cur = head;newHead = cur;head =headNext;if(headNext == NULL)break;headNext = headNext->next;continue;}while(cur){//中间插入if(cur->val < head->val){curPrev = cur;cur = cur->next;}else{head->next = cur;curPrev->next = head;head = headNext;if(headNext == NULL)break;headNext = headNext->next;break;}}//尾插if(cur == NULL){curPrev->next = head;head->next = NULL;head = headNext;if(headNext == NULL)break;headNext = headNext->next;}}return newHead;
}

 总结:本篇博客介绍了两个有关链表的两个题,相对于前面我们所介绍的题,可能有些难度,但这些难度是不是都是在思路上,如果有了这个思路实现起来是不是还是用我们前面的思想啊,因此我们别畏惧它,相信通过夜以继日的敲代码,我们肯定会拿到一个难题就会有思路的。大家加油!💯


🌻数据结构与算法专栏🌻

🤜别放弃是我们的底色,加油!🤛

🏋不是每一粒种子都能开花,但播下种子就比荒芜的旷野强百倍🏋

版权声明:

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

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