【经典题目】链表OJ（相交链表、环形链表、环形链表II、随机链表的复制）

小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了有关链表的各种经典面试题目相交链表、环形链表、环形链表II、随机链表的复制内容全由作者原创无AI同时深度解析了题目的经典解决方法并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1.相交链表2.环形链表3.环形链表II4.随机链表的复制结语1.相交链表题目链接相交链表方法1遍历链表A的所有节点并且将A链表的所有节点都与B链表的所有节点进行比较如果有节点相同说明他们是相交的如果没有节点相同说明这两个链表不相交。要求上面的方法的时间复杂度是ON^2有没有更快的方法呢方法2比较推荐1.判断是否相交。如果这两个链表相交了说明他们最后一个节点一定是相同的。我们可以分别遍历两个链表找出这两个链表的最后一个节点并进行比较。如果不相同直接返回NULL;如果2相同再找出他们相交的节点。2.若相交找出第一个节点。先分别算出这两个链表的长度再求出这两个链表长度的差值gap。然后找出他们两其中较长的链表并重新遍历这两个链表。长链表先走gap步然后两个链表同时开始遍历。当找到两个相同的节点时返回该节点的地址我们更推荐使用方法2因为他的时间复杂度是ON要优于方法1下面是用方法2解决这道题的完整代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA headA; struct ListNode* curB headB; int countA 1; int countB 1; while(curA-next) { curA curA-next; countA; } while(curB-next) { curB curB-next; countB; } if(curA!curB) { return NULL; } struct ListNode* fast headA; struct ListNode* slow headB; int gap abs(countA - countB); if(countA countB) { fast headB; slow headA; } while(gap--) { fast fast-next; } while(fast!slow) { fast fast-next; slow slow-next; } return fast; }2.环形链表题目链接环形链表解题思路快慢指针慢指针一次走一步快指针一次走两步。当slow进环的时候fast开始追击slow。fast追上slow就有环如果fast走到NULL就说明没有环。为什么一定会相遇有没有可能永远错过请证明假设slow进环时fast和slow的距离是N。每当fast走两步slow走一步时fast和slow的距离都会缩小1直到fast和slow的距离为零。因此fast和slow一定会相遇下面是这道题目的完整代码/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* fast head; struct ListNode* slow head; while(fastfast-next) { slowslow-next; fastfast-next-next; if(slowfast) { return true; } } return false; }拓展当slow走1步fast走3步、4步、5步、n步时fast和slow还一定会相遇吗我们先探究当fast走三步时的情况同样的我们假设slow进环时fast和slow的距离是N。每当fast走三步slow走一步时fast和slow的距离都会缩小2。这里就要分两种情况当N为偶数时每走一次fast和slow的距离都会缩小2直到N为0。因此当N为偶数时fast和slow一定会相遇。当N为奇数时每走一次fast和slow的距离都会缩小2直到N为-1。N为-1的意思也就是fast超前了slow一步fast和slow并没有相遇。我们现在假设圆环的长度是C那么现在fast到slow的距离就是C-1。当C-1为偶数时每走一次fast和slow的距离都会缩小2直到N为0。因此当C-1为偶数时fast和slow一定会相遇。当C-1奇数时每走一次fast和slow的距离都会缩小2直到N为-1。此时就陷入了死循环了fast永远也不会和slow相遇。总结一下1.N是偶数第一轮就追上了2.N是奇数第一轮追击会错过距离变成C-1a.如果C-1为偶数那么下一轮就追上了b.如果C-1为奇数那么就永远追不上此时我们发现fast追不上slow只有一种情况就是N为偶数且C-1为奇数可是这种情况存在吗同样的我们假设slow进环时fast和slow的距离是N并且我们设slow刚进环时fast已经在环里面转了x圈。此时slow走的距离是Lfast走的距离是Lx*CC-N。又因为fast走的距离是slow的三倍那么这时我们就可以列一个等式3LLx*CC-N2Lx*CC-N现在N为奇数C为偶数偶数x1*偶数 - 奇数很明显我们看到这个等式是矛盾的。说明N为偶数且C-1为奇数的情况不存在结论一定能追上N等于偶数时第一轮就能追上N等于奇数时C-1一定为偶数第二轮就能追上那么当fast走4步、5步、n步呢这里的分析方法都是一模一样的欢迎博友们在评论区展开讨论这里就不详细探究了~3.环形链表II题目链接环形链表II方法1与上一题的思路一样可以先用快慢指针先找到在环里相遇的一个节点然后将这个节点与后一个节点断开这样问题就转化成了相交链表的问题完整代码如下/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA headA; struct ListNode* curB headB; int countA 1; int countB 1; while(curA-next) { curA curA-next; countA; } while(curB-next) { curB curB-next; countB; } if(curA!curB) { return NULL; } struct ListNode* fast headA; struct ListNode* slow headB; int gap abs(countA - countB); if(countA countB) { fast headB; slow headA; } while(gap--) { fast fast-next; } while(fast!slow) { fast fast-next; slow slow-next; } return fast; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast head; struct ListNode* slow head; while(fastfast-next) { fastfast-next-next; slowslow-next; if(slowfast) { struct ListNode* newnode slow-next; slow-nextNULL; return getIntersectionNode(newnode,head); } } return NULL; }方法二这个方法比较巧妙实现起来比方法一更快也是更推荐使用的方法。我们可以设进环的位置到相遇节点的距离为N。那么slow走的路程就是LN而fast走的路程就是Lx*CN根据fast走的距离时slow的两倍我们可以得出一个等式2LN Lx*CNL x*C-NL x-1*CC-N根据这个等式我们可以得出起点到进入环的第一个节点的距离等于x-1个圆环长度加上meet到起点到进入环的第一个节点的距离。此时我们让两个指针从head和meet开始遍历链表最后相遇的节点肯定是进入环的第一个节点。题目完整代码如下/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast head; struct ListNode* slow head; while(fastfast-next) { fastfast-next-next; slowslow-next; if(slowfast) { struct ListNode* meet slow; while(meet!head) { meetmeet-next; headhead-next; } return meet; } } return NULL; }4.随机链表的复制题目链接随机链表的复制这题也是这四道题目难度最大的一题也是链表掌握程度的一块试金石。简单来说深拷贝就是拷贝一个值和指针指向跟当前链表一模一样的链表。下面一起跟着我的思路看看这道题目。这道题目的难点关键在于怎么找到random指向的节点。因为我们要创建一个全新的链表又不能使用原来链表的节点所以我们不能直接拷贝random的值。那我们如果在每个random指向的节点后面创建一个与random指向节点一样的节点是不是就可以通过random-next-next来找到我们新链表random指向的节点。为了方便我们干脆在每个节点后都创建一个一模一样的节点如下图所示这样做的好处也是让原链表和新链表建立起了一种关联关系。如果节点的random指向为空那我们就让新节点的random也指向为NULL接着让指针指向下一个新创建的节点。如果节点的random指向不为空那我们就让新节点的random指向原节点random的next指针也就是对应random所指向的新创建节点接着让指针指向下一个新创建的节点。当我们把所有新节点的random都设置好后就可以把新链表串起来并把原链表恢复原样。具体的实现思路1.拷入节点插入在原节点后面2.用两个指针分别遍历新链表和原链表给新节点的random赋值3.把拷贝节点取下来尾插成为新链表然后恢复原链表不恢复也可以下面是这道题目的完整代码/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur head; while(cur) { struct Node* copy (struct Node*)malloc(sizeof(struct Node)); copy-valcur-val; copy-next cur-next; cur-nextcopy; curcopy-next; } cur head; while(cur) { struct Node* copy cur-next; if(cur-randomNULL) { copy-randomNULL; } else { copy-randomcur-random-next; } curcopy-next; } struct Node* copyhead NULL; struct Node* copytail NULL; curhead; while(cur) { struct Node* copy cur-next; struct Node* next copy-next; if(copyheadNULL) { copyheadcopytailcopy; } else { copytail-nextcopy; copytailcopy; } cur-nextnext; curnext; } return copyhead; }这道题目综合链表的多种方法逻辑也比较复杂也有不少易错点需要勤加练习。结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~