wordpress自建站上可以买卖,世界球队实力排名,网站开发后端框架,自己建设手机网站在链表算法题#xff08;上#xff09;长中我们已经学习了一系列的链表算法题#xff0c;那么在本篇中我们将继续来学习链表的算法题#xff0c;接下来就继续来破解链表的算法题吧#xff01; 1.相交链表
160. 相交链表 - 力扣#xff08;LeetCode#xff09; 通过以上…在链表算法题上长中我们已经学习了一系列的链表算法题那么在本篇中我们将继续来学习链表的算法题接下来就继续来破解链表的算法题吧 1.相交链表
160. 相交链表 - 力扣LeetCode 通过以上的题目的描述该算法题要我们实现的代码功能是判断两条链表是否相交如果相较的话就返回相较节点的指针不相较就返回NULL
那么在实现该算法题的代码之前先要来分析如何实现判断是否是相交链表
首先来看相交链表有什么特征呢来看以下的示例
从以上的示例就可以看出当两个链表是相交的那么在这两条链表内一定会有两个节点的下一个节点是相同的。而如果链表不是相交的那么就不会有两个节点的下一个节点是相同的
当两个链表是相较的时候我们需要返回的就是以上这个节点那么该如何来找出这个相交的节点呢
在此我们的解决方法是先定义两个指针变量一开始分别指向两个链表的第一个节点之后通过各遍历一次两条链表之后就得到这两条链表各自的节点个数之后将得到的两个节点数大的减小的得到两链表长度的差值将节点个数多的链表的定义的节点指针往后走之前得到的差值最后将两个链表的指针同时往后遍历当两个指针相同时就说明这两个链表为相交链表否则就不相交 例如以下示例 首先A链表个数为5B节点个数为6两个链表节点差值就为1 在定义两个指向两个链表的第一个节点的指针pcur1和pcur2由于B链表为节点个数多的链表因此将B链表的指针pcur2先向后走1步 之后让pcur1和pcur2同时向后遍历之后pcur1和pcur2同时指向c1节点这就可以说明A和B这两个链表是相交链表 接下来我们就来实现该算法题的代码在以下得到两个链表的节点数差值使用的是库函数abs该函数能计算出差值的绝对值
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{ListNode* pcur1headA;ListNode *pcur2headB;int count10;int count20;while(pcur1)//得到第一个链表的结点数{count1;pcur1pcur1-next;}while(pcur2)//得到第二个链表的节点数{count2;pcur2pcur2-next;}int tmpabs(count1-count2);//得到两个链表节点数的差值ListNode* longlistheadA;ListNode* shortlistheadB;if(count1count2)//确定长短链表{longlistheadB;shortlistheadA;}while(tmp--)//先将长链表走tmp步{longlistlonglist-next;}while(longlist shortlist)//同时遍历两个链表{if(longlistshortlist){return longlist;}longlistlonglist-next;shortlistshortlist-next;}return NULL;
} 2.环形链表I
141. 环形链表 - 力扣LeetCode 根据以上的题目描述就可以看出该算法题要我们实现的是判断链表是否为循环链表在此循环链表是指链表的尾节点不在是连接NULL而是连接链表中的其中一个节点
那么使用什么方法能判断链表是否为循环链表呢
在此我们使用的是之前学习过的前后指针法首先定义有两个指针变量fast和slow之后fast指针每次走两步slow指针每次走一步到最后如果fast指针和slow相遇就说明该链表为循环链表 例如以下示例 要判断以上链表是否为循环链表我们来看看使用前后指针法的过程是什么样的首先定义快指针fast和满指针slow之后让fast和slow遍历链表 正如上图所示slow指针和fast指针在节点-4相遇这就说明该链表为循环链表为循环链表 接下来我们就来实现该算法题的代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{ListNode* fast,*slow;fastslowhead;while(fast fast-next){fastfast-next-next;slowslow-next;if(fastslow){return true;}}return false;
} 在解决了以上的算法题后我们就要思考为什么快指针每次走两步慢指针走一步可以相遇有没有可能遇不上呢 slow一次走⼀步fast一次走2步fast先进环假设slow也走完入环前的距离准备进环此时fast和slow之间的距离为N接下来的追逐过程中每追击⼀次他们之间的距离缩小1步 这时在追击过程中fast和slow之间的距离变化 因此在带环链表中慢指针走一步快指针走两步最终一定会相遇。 那么在解决以上问题后思考快指针一次走3步走4步...n步行吗? step1:按照上面的分析慢指针每次走一步快指针每次走三步此时快慢指针的最大距离为N接下来的追逐过程中每追击一次他们之间的距离缩小2步追击过程中fast和slow之间的距离变化 分析:1、如果N是偶数第一轮就追上了 2、如果N是奇数第一轮追不上快追上错过了距离变成-1即C-1进入新的一轮追击 aC-1如果是偶数C-1如果是偶数那么下一轮就追上了 bC-1如果是奇数那么就永远都追不上 总结一下追不上的前提条件N是奇数C是偶数 step2 在以上的step1中我们得出当fast追不上的前提条件N是奇数C是偶数那么接下来我们就要继续分析这种情况是否会出现 假设 环的周长为C头结点到slow结点的长度为Lslow走一步fast走三步当slow指针入环后slow和fast指针在环中开始进行追逐假设此时fast指针已经绕环x周。 在追逐过程中快慢指针相遇时所走的路径长度: 由于慢指针走一步快指针要走三步因此得出 3 * 慢指针路程 快指针路程 即 对上述公式继续分析由于偶数乘以任何数都为偶数因此 2L 一定为偶数则可推导出可能得情 况• 情况1偶数 偶数 - 偶数 • 情况2偶数 奇数 - 奇数 由step1中1得出的结论如果N是偶数则第一圈快慢指针就相遇了。 由step1中2得出的结论如果N是奇数则fast指针和slow指针在第一轮的时候套圈了开始进行下一轮的追逐当N是奇数要满足以上的公式则 (x1)C 必须也要为奇数即C为奇数满足2a中的结论则快慢指针会相遇 因此 step1 中的 N是奇数C是偶数不成立既然不存在该情况则快指针一次走3步最终一定也可以相遇。 因此快指针一次走4、5.....步最终也会相遇其证明方式同上 注虽然已经证明了快指针不论走多少步都可以满足在带环链表中相遇但是在编写代码的时候会有额外的步骤引入涉及到快慢指针的算法题中通常习惯使用慢指针走⼀步快指针走两步的方式。 3.环形链表II
142. 环形链表 II - 力扣LeetCode 在以上环形链表I中我们已经实现了如何判断一个链表是否为环形链表接下来我们在环形链表算法题中我们将跟进一步当链表是环形链表时我们还要返回链表进入环的第一个节点
那么要如何才能找到环形链表进入环的第一个节点呢接下来我们要来了解一个性质 让一个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 例如以下示例 根据使用快慢指针法我们就可以的到以上链表两指针的相遇节点为-4 在此之后我们再定义一个指针变量pcur指向链表的第一个节点之后让pcur指针和fast指针同时遍历当这两个指针指向同一个节点时指针指向的节点就是入环前的节点 接下来我们就来实现该算法题的代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{ListNode* fast,*slow;fastslowhead;while(fast fast-next){fastfast-next-next;slowslow-next;if(slowfast){ListNode* pcurhead;while(pcur!fast){pcurpcur-next;fastfast-next;}return fast;}}return NULL;
} 在解决了以上的算法题后我们就要证明为什么在环形链表中以上的这种性质
在以上图示当中H为链表的起始点E为环入口点M与判环时候相遇点
在此我们设环的长度为RH到E的距离为LE到M的距离为 X 则M到E的距离为 R-X
由于快指针和满指针走过的路径分别为
又因为快指针走过的路径长度为满指针走过的路径长度的两倍这时就能得到以下的公式 根据以上公式就可以推断出以下公式 在此可以继续得到
当慢指针进入环时快指针可能已经在环中绕了n圈了n⾄少为1因为快指针先进环走到M的位置,最后又在M的位置与慢指针相遇
所以以上公式n可能为1,2,3,4......n的大小取决于环的大小环越小n越大在此极端情况下假设n1此时 LR-X
根据LR-X即可说明⼀个指针从链表起始位置运行⼀个指针从相遇点位置绕环每次都走⼀步两个指针最终会在入口点的位置相遇 4.随机链表的复制
138. 随机链表的复制 - 力扣LeetCode 根据以上的题目描述可以看出该算法题和我们之前解决的题不同在该算法题中的链表节点中的有三个成员变量相比正常的链表节点多了一个随机的指针random。在此题目要我们实现的是链表的拷贝注意在此不是将原链表内的指针复制一份这种只是浅拷贝在此算法题中我们要实现的是深拷贝也就是要额外开一份和原链表一样的内存空间在将原链表内的数据拷贝给新的链表 接下来我们就来分析如何来实现链表的拷贝
例如以下示例 在以上链表中若要实现链表的拷贝那么该如何实现呢
在此你可能会想到可以通过遍历原链表在每遍历到一个节点时就创建一个新的节点再将原链表节点内的数据拷贝给新节点之后再将新节点尾插新链表
但是在以上的示例按照这种方法来实现就会发现问题了在以上示例的链表按照以上的方法来拷贝在第一个节点时没问题当到了第二个节点就出现一个问题就是原链表第二个节点中的random指针指向的第一个节点但在使用以上方法时第二个节点中的random无法找到第一个节点这时因为单向链表中无法向前遍历链表 因此要解决链表的拷贝以上的方法行不通在此我们需要想其他的方法 接下来就来讲解一种很妙的方法 首先是在原链表基础上复制链表 在此我们先定义两个指针变量pcur和Next分别指向原链表第一个节点和第二个节点 之后创建一个新的节点并且将第一个节点内的值val拷贝到新节点中再将新节点插入到pcur和Next节点中间完成以上操作后让pcur指向Next指向的节点Next指向其next指针指向的节点 之后在遍历原链表每个节点时重复以上的操作直到pcur指向NULL停止操作这时原链表就变为以下形式 在以上我们创建的新节点只进行了val的拷贝那么接下来就来对random来进行拷贝要进行random的拷贝接下来要再创建一个指针变量copy让其一开始指向创建的第一个新节点并且之后还要让pcur和Next指针重新回到初始位置 之后继续置random指针 在此pcur指向节点的random为NULL就让这时copy指向的节点内的random也置为NULL之后让pcur指向Next指向的节点Next指向其next指针的next指向的节点copy指向改变后的pcur的next指针指向的节点 之后再遍历原链表当pcur指向节点内的random不为NULL时让copy内的random指针指向pcur内random指向的节点next指针指向的节点也就是copy-randompcur-random-next最后当pcur为NULL停止这时原链表就变为以下形式 完成以上操作后最后就要将原链表和赋值链表断开 在此让pcur的next指针指向copy的next指针指向的节点copy的next指针指向pcur的next指针指向的节点next指针指向的节点之后让copy和pcur都往后走一步 之后再遍历原链表重复以上的操作这时原链表就变为以下形式 通过以上示例的讲解就可以发现链表的复制分为以下3步 接下来就来实现该算法题的代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/typedef struct Node Node;Node* NewNode(int x){Node* newnode(Node*)malloc(sizeof(Node));newnode-valx;newnode-nextnewnode-randomNULL;return newnode;}struct Node* copyRandomList(struct Node* head)
{if(headNULL){return head;}Node* pcurhead;
//在原链表基础上复制链表while(pcur){Node* Nextpcur-next;Node*newnodeNewNode(pcur-val);newnode-nextNext;pcur-nextnewnode;pcurpcur-next-next;}
//置random指针pcurhead;while(pcur!NULL){Node* newpcurpcur-next;if(pcur-random!NULL){newpcur-randompcur-random-next;}pcurnewpcur-next;}
//将原链表和赋值链表断开pcurhead;Node* newhead,*newptail;newheadnewptailpcur-next;while(pcur-next-next){pcurpcur-next-next;newptail-nextpcur-next;newptailnewptail-next;}return newhead;
} 以上就是链表算法题的全部内容了希望能得到你的点赞、收藏
