深圳app网站建设陈俊兵,南昌专业做网站公司,里水九江网站建设,没建网站 备案目录 前言相交链表思路分析代码实现 环形链表思路分析代码实现 环形链表Ⅱ思路分析代码实现 复制带随机指针的链表思路分析代码实现 前言
本篇文章承接上篇博客#xff0c;继续对部分经典链表OJ题进行讲解
相交链表
先来看题目描述
思路分析
这道题我们还是首先来判断一… 目录 前言相交链表思路分析代码实现 环形链表思路分析代码实现 环形链表Ⅱ思路分析代码实现 复制带随机指针的链表思路分析代码实现 前言
本篇文章承接上篇博客继续对部分经典链表OJ题进行讲解
相交链表
先来看题目描述
思路分析
这道题我们还是首先来判断一下链表是否相交即看两条链表的最后一个节点是否为同一个。如果不相交则返回空如果相交则进行下一步。 如果两条链表相交我们可以考虑让较长的链表走它们的长度差步使得两条链表此时的长度一样然后再同时走直到两条链表的节点指向同一块区域这个节点就是相交点。
代码实现
代码实现如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailAheadA;int lenA0;struct ListNode* tailBheadB;int lenB0;while(tailA){tailAtailA-next;lenA;}while(tailB){tailBtailB-next;lenB;}if(tailA!tailB){return NULL;}int tmpabs(lenA-lenB);struct ListNode* llistheadlenAlenB?headA:headB;struct ListNode* slistheadlenAlenB?headB:headA;while(tmp--){llistheadllisthead-next;}while(1){if(llistheadslisthead){break;}llistheadllisthead-next;slistheadslisthead-next;}return llisthead;}环形链表
先来看题
思路分析
这道题我们采用快慢指针的思路这样如果是环形链表当快指针和慢指针都进入环时快指针总能与慢指针遇到为保证效率和可实现度我们让快指针一次走两步慢指针一次走一步。 如果快指针指向空且快指针的下一个节点也指向空因为要保证快指针能一次走两步,说明该链表并没有形成环。
代码实现
代码如下
bool hasCycle(struct ListNode *head) {if(headNULL)return false;struct ListNode* slowhead;struct ListNode* fasthead;while(fastslowfast-next){slowslow-next;fastfast-next-next;if(slowfast)return true;}return false;
}环形链表Ⅱ
这道题是上一道题的变式也借鉴了上一题的思路。 来看题
思路分析
我们还是按照上一题的解题思路判断链表是否形成了环。如果没有则返回空如果是环形链表我们继续进行下一步。
在确定存在环时此时快指针和慢指针正好相遇实际上此时头节点到链表进入环的节点的距离和此时快/慢指针到链表进入环的结点的距离相等。所以此时我们只需要让头指针和快/慢指针同时走到相遇时即为我们要找的节点。
代码实现
代码实现如下
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slowhead;struct ListNode* fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){while(slow!head){slowslow-next;headhead-next;}return head;}}return NULL;}复制带随机指针的链表 思路分析
这道题的本意是让我们复制一次这个链表我们这里采用的思路是就在原有的链表上操作1先在每一个节点后复制一个一样的节点2再把所有复制出来的节点与原链表断开3再链接起来这样我们就可以得到一个和原链表一摸一样的新链表了虽然思路听起来很简单但是想要真正弄清楚里面所有指针到底该指向哪里同时又要避免野指针的情况出现还是非常有难度的下面我把操作分为三部分来讲解。 在每一个节点后复制一个一模一样的节点链接起来 首先我们可以先判断一下链表是否为空如果为空就直接返回空指针否则我们按下图进行操作以三个节点为例 把所有复制出来的节点有原链表断开 最后将复制出来的节点连接再一次即可。
代码实现
代码实现如下
struct Node* copyRandomList(struct Node* head) {if(headNULL){return NULL;}for(struct Node* curhead;cur!NULL;curcur-next-next){struct Node* newnode(struct Node*)malloc(sizeof(struct Node));newnode-valcur-val;newnode-nextcur-next;cur-nextnewnode;}for(struct Node* curhead;cur!NULL;curcur-next-next){struct Node* newnodecur-next;newnode-random(cur-random!NULL)?cur-random-next:NULL;}struct Node* newheadhead-next;for(struct Node* curhead;cur!NULL;curcur-next){struct Node* newnodecur-next;cur-nextcur-next-next;newnode-next(newnode-next!NULL)?newnode-next-next:NULL;}return newhead;
}以上就是本章全部内容如有出入欢迎大佬指正。
