北京去哪个医院看白癜风最好 https://baike.baidu.com/item/%E5%8C%97%E4%BA%AC%E4%B8%AD%E7%A7%91%E7%99%BD%E7%99%9C%E9%A3%8E%E5%8C%BB%E9%99%A2/9728824写在前面：经过编辑部讨论，我准备推出《一个XX的XX问题》系列推送，主要分享一些leetcode上有趣的小问题，都很简单，阅读时间都在3分钟以内，仅供各位大佬乐呵一下。目前的两篇推送考虑到可读性我都没有附代码，如果有人想看的话，我可以从下一篇开始附上，也全当是监督我练习匈牙利命名法。（yysy，abcd命名法真好用！）下面进入正题：问题：如何判断单链表中是否有环？若有，则链表最后一个元素指向哪个位置？要求不得更改原数据。（注：以下解题过程不适用于python）对于这个问题，大部分人的第一思路是利用额外的空间进行标记，方法通常是哈希。通过将每个节点的地址作为key建立哈希映射，每当链表中访问到一个元素时，便把这个地址加入哈希列表。若哈希中出现了重复key，则第一个重复key对应的节点极为所求。若直到遍历结束哈希中也没有出现重复，则可判定链表无环。这种方法空间复杂度O(n)，时间复杂度随哈希映射方式不同和处理冲突方式的不同而改变，但阶数一定高于O(n).此外，以地址为key的哈希算法需要考虑到在拥有不同CPU总线宽度的电脑上运行，获取的物理地址或者逻辑地址的长度是不一样的。这里要注意，在大部分编程语言中是不能采用对每个节点进行扩大，利用扩充的空间进行标记是否被访问的方法。因为在地址重新分配到过程中存在一定概率，使得原地址处无法申请到额外空间，于是编译器会自动在别的地方申请空间，将旧地址的元素复制过去，造成了原始数据的改变。那么我们只用O(1)空间复杂度，O(n)时间复杂度完成命题呢？一定是可以的。思路是使用快慢指针，这在链表操作中是一个十分重要的技巧。我们先看一个我费了老大劲做的视频，再讲证明。（以主编的头发保证，视频大小只有两兆，不用担心流量）下面用文字来叙述上述过程：1、快慢指针同时从head出发，若相遇则有环。2、A从head出发，B从相遇位置出发，以相同速度运动，第二次相遇位置一定是交点位置。这里第一条是显然的，不过小学奥数而已。接下来着重说明为什么第二次相遇的位置一定是交点。设圆周长度为C，head到交点长度为L，交点到第一次相遇地点距离为x，显然C、L、x均为非负整数，于是可以使用同余证明。快慢指针速度满足二倍关系，有：,推出,即,所以.并且由知.因此，第二次相遇一定在交点处，本题证毕。下面再给出一个类似的题目：如何判断两个无环单链表是否相交？若相交则交点在哪？放点我最喜欢的折耳猫容各位想一下：答案：将第一条链表首尾相连，然后从第二个链表的head出发找是否有环,即可转化为上一问题。总结：快慢指针法在某些情况下可以获得很漂亮的时间空间复杂度，但技巧性过强，实际貌似很不常见，只是因为本题解法过于精彩而放上来。预览时标签不可点
转载请注明：http://www.92nongye.com/hxjs/204622014.html
