用户体验度好的网站,网站建设推广代理公司,网络营销最主要的工具是,wordpress description引言#xff1a;本篇博客详细讲解了关于链表的三个经典例题#xff0c;分别是#xff1a;环形链表#xff08;简单#xff09;#xff0c;环形链表Ⅱ#xff08;中等#xff09;#xff0c;随机链表的复制#xff08;中等#xff09;。当你能毫无压力地听懂和成功地… 引言本篇博客详细讲解了关于链表的三个经典例题分别是环形链表简单环形链表Ⅱ中等随机链表的复制中等。当你能毫无压力地听懂和成功地写出代码时那就一定可以充分的证明你的链表知识学习地非常扎实了 更多有关C语言的知识详解可前往个人主页计信猫 目录
一环形链表简单
1题目描述
2思路分析
3代码解答 二环形链表简单的拓展
1提出问题
2问题Ⅰ的解答
3问题Ⅱ的解答
4问题Ⅱ中C与N的关系
三环形链表 Ⅱ中等
1题目描述
2思路分析
3代码解答
四随机链表的复制中等
1题目描述
2思路分析
3代码解答
五结语 一环形链表简单
1题目描述
OJ链接环形链表 给你一个链表判断链表中是否存在环若存在则返回true反之则返回false。
2思路分析 为了解出这道题我们可以使用一个在链表中可谓是大名鼎鼎的方法——快慢指针。 所谓的快慢指针就是定义两个结构体指针slow和fast而fast指针每次比slow指针多走一步。假如我们将fast比作兔子slow比作乌龟。 那么显而易见假如整个链表里边没有环则兔子fast指针一定会先走到NULL假如整个链表里边有环则兔子fast指针一定会先进入环并一直在环里边循环着走一直到乌龟slow指针进入环由于兔子和乌龟具有速度差所以在某一时间刻乌龟和兔子一定会相遇所以如果兔子和乌龟相遇了即链表有环。
3代码解答
if(headNULL)//判断链表是否为空{return false;}struct ListNode*fasthead-next;//定义快指针struct ListNode*slowhead;//定义慢指针while(fastfast-next){if(fastslow)//两指针相遇则成环{return true;}fastfast-next-next;//快指针每次走两步slowslow-next;//慢指针每次走一步}return false; 二环形链表简单的拓展
1提出问题 假如你正在参加某个hr的面试而面试官刚刚好问到你这个问题经过充分准备的你毫不费力地将这道题秒杀了。但面试官接下来又提出了两个问题 1为什么fast和slow指针一定会相遇请给出证明 2当fast指针一次走n步时快慢指针还会不会相遇 这时候阁下又该如何是好呢 2问题Ⅰ的解答 其实遇到这种问题我们完全没必要慌张我们只需要拿出作为程序员严谨的态度给予证明就可以了。 我们可以假设在fast和slow都进入环的时候两指针的间距为N。既然每进行一次追击fast都前进两步slow前进一步那么它们之间的距离一定会缩小一步。 那么当我们进行了N次追击则间距则会如此变化NN-1N-2……10。 所以如此来看两指针的间距一定会变为0那么fast和slow指针也一定会相遇第一关通过获得50%的offer
3问题Ⅱ的解答 此时对于n的具体取值我们就需要分开讨论了我们就先以n等于3来进行讨论吧 我们设进入环的时候两指针的间距d等于N故每一次追击之后dN-n-1N-2再设整个环的长度为C。 当d为偶数时距离每次减少2则可以追上。 但当d为奇数时就要另当别论了 d为奇数时第一次的追击则会错过NN-2N-4……1-1。而这里的-1意味着fast指针会跑到slow指针的前一位去并开始新一轮的追击。 那么此时我们就需要再次讨论dC-1的奇偶关系了。 当C为奇数时dC-1为偶数则可以追上。 当C为偶数时dC-1为奇数则又会进入下一次追击进入死循环永远也追不上 所以其他n的取值情况也就同样方法继续思考了。第二关通过获得100%的offer)
4问题Ⅱ中C与N的关系 看了上面问题Ⅱ的解析后我们都知道了快慢指针是否可以相遇与CN的奇偶性相关。而C与N之间是否有存在着奇偶性的关系呢答案是肯定的。 我们还是以n3来进行分析假设进环之前的路程长度为L当slow进入环的时候fast已经在环里边走了x圈。 而此时slow和fast指针走的路程分别如下 因为n3那么此时fast走的路程就是slow走的路程的三倍所以我们可以得到等式 3*LLx*CC-N 那么进行等式化简之后我们便可以得到 2*Lx1*C-N 所以在问题Ⅱ中若dN为奇数C为偶数的条件一定是不存在的原因如下 三环形链表 Ⅱ中等
1题目描述
OJ链接环形链表Ⅱ 这次的不一样的地方就是需要在普通环形链表的基础上返回链表成环的节点。
2思路分析 关于这道题我将会介绍一个十分巧妙的方法一个指针从链表的头节点head开始出发另一个指针从fast和slow指针相遇的节点meet出发最终它们一定会在成环的起始节点相遇。
证明 还是老样子我们假设在fast和slow相遇的时候fast已经走了x圈。 那么此时slow和fast走的路程分别为 所以我们便可以得到如下等式 2LNLx*CN Lx*C-N 故等号左边的L就表示第一个指针从头节点head到成环起始节点的距离等号右边的x*C不就相当于是周期吗并没有影响剩下的N不就表示着meet节点到成环起始节点的距离吗所以等号左右两边相等以上方法成立
3代码解答
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode*fasthead;struct ListNode*slowhead;//寻找meet节点while(fastfast-next) {slowslow-next;fastfast-next-next;if(slowfast){struct ListNode*meetslow;//找到meet节点struct ListNode*curhead;//使用cur从头节点出发while(meet!cur){curcur-next;meetmeet-next;}return meet;//cur和meet相遇的节点则为成环起始节点}}return NULL;
}
四随机链表的复制中等
1题目描述
OJ链接随机链表的复制 给定你一个链表链表中含有一个随即指针random它指向链表的其他节点或者NULL如下 而你需要做的就是复制一个与原链表一模一样的链表并且与对原链表毫无影响。
2思路分析 其实这道题本身不难复制一个链表简直易如反掌而唯一的难点就是这个结构体成员random指针。它导致了复制random时可能链表的那个random节点还没出现的问题。 但是我们可以以以下方式解决问题 如上所示我们可以先在每一个原链表节点之后插入一个与原节点一模一样的节点先不管random指针然后我们再对插入节点的random指针赋值最后再将插入的指针取下来就可以了。 可能很多人会问道random指针如何赋值呢其实很简单当我们将节点插入之后random指针的值不就是原指针random所指向的值的next吗这样random的赋值就完美的解决了
3代码解答
struct Node* BuyNode(int val)//设计一个创建节点的函数
{struct Node*newnode(struct Node*)malloc(sizeof(struct Node));newnode-nextNULL;newnode-valval;return newnode;
}
struct Node* copyRandomList(struct Node* head)
{
//防止空链表if(headNULL){return NULL;}//创建后继节点struct Node*curhead;while(cur){struct Node*newnodeBuyNode(cur-val);newnode-nextcur-next;cur-nextnewnode;curcur-next-next;}//赋值randomstruct Node*newcurhead;struct Node*follownewcur-next;while(follow){if(newcur-randomNULL)//random指向NULL就特殊处理赋值NULL{follow-randomNULL;//指针遍历链表的移动newcurnewcur-next-next;if(follow-next){followfollow-next-next;}else{break;}}else{follow-randomnewcur-random-next;//指针遍历链表的移动newcurnewcur-next-next;if(follow-next){followfollow-next-next;}else{break;}}}//将后继结点分离struct Node*pheadhead-next;struct Node*ptailhead-next;while(ptail-next){ptail-nextptail-next-next;ptailptail-next;}return phead;
}
五结语 其实这些题讲起来看起来非常轻松但也耗费了我不少时间去做出它甚至还是在看了题解的前提下。 但让我值得欣慰的是我还是结合题解做出了这些题甚至第二题我还自己想出来自己的方法而且我也十分顺利的在博客里清楚的讲解出了每道题的做法。这也证明了我的链表学习还是取得了效果。 希望我的这篇博客也可以同样帮助到热爱编程学习的你让我们一起进步一起加油
