h5企业模板网站,上街网站建设,无极电影网首页,网络推广工作室 是干啥的文章目录 Linked List Cycle II 环形链表 II问题描述#xff1a;分析代码哈希快慢指针 Tag Linked List Cycle II 环形链表 II
问题描述#xff1a;
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链… 文章目录 Linked List Cycle II 环形链表 II问题描述分析代码哈希快慢指针 Tag Linked List Cycle II 环形链表 II
问题描述
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。 链表中节点的数目范围是 [ 0 , 1 0 4 ] − 1 0 5 N o d e . v a l 1 0 5 p o s 为 − 1 或者链表中的一个有效索引 链表中节点的数目范围是 [0, 10^4]\\ -10^5 Node.val 10^5\\ pos 为 -1 或者链表中的一个 有效索引 链表中节点的数目范围是[0,104]−105Node.val105pos为−1或者链表中的一个有效索引
分析 和昨天的环形链表类似利用哈希可以在 O ( N ) O(N) O(N)的时间下找到第一个节点。 另一种就是空间为常数的快慢指针就是昨天发的那个它还有个比较学术的名字Floyd判圈算法(Floyd Cycle Detection Algorithm)它的应用场景很广泛可以自行BingGoogle。 它的思路比较简单如果存在环那么先找到快慢指针在环中的相遇的点 x然后再让2个指针分别从headx出发直到2者相遇就是环的入口点。 思路很简单但是大部分人还是不一定能AC。
为什么按照这个思路可以找到的点一定是入口点? 讨论的前提是有环。 假设入口点是y那么从 h e a d head head到达y需要 a步从y到达2指针的相遇点x要走b步,b一定是小于n的,从x继续走c步到达入口y,所以环的大小为 b c bc bc。 f a s t 走的路程 a ( k 1 ) ( b c ) b fast 走的路程 a (k1)(bc) b fast走的路程a(k1)(bc)b。 a 是无环段b是环的入口到x的路程而 ( k 1 ) ( b c ) (k1)(bc) (k1)(bc) 就是跑环的圈数 k 0 k0 k0。 而 s l o w 的路程 a b slow的路程 ab slow的路程ab ,因为fast的速度是slow的2倍所以路程也是其2倍即 a b ( k 1 ) ( b c ) 2 ∗ ( a b ) ( k 1 ) ( b c ) a b k ( b c ) c a ab (k1)(bc) 2*(ab)\\ (k1)(bc) ab\\ k(bc)c a ab(k1)(bc)2∗(ab)(k1)(bc)abk(bc)ca
到这里就会可以得到一个结论设置2个指针分别从点x和head出发每次一步如果相遇就是入口点。
如果你无法理解这个结论. 提示你可以从路程的角度来思考即一个从x出发的指针它可能走c或者是k(bc)c,然后恰好与另一个指针在入口相遇。 时间复杂度 O ( N ) 时间复杂度O(N) 时间复杂度O(N) 空间复杂度 O ( 1 ) 空间复杂度O(1) 空间复杂度O(1)
代码 哈希
public boolean hasCycle(ListNode head) {SetListNode set new HashSet();ListNode p head;while(p!null){if(!set.add(p)) return p;p p.next;}return null;} 时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( N ) O(N) O(N)
快慢指针
public ListNode detectCycle(ListNode head) {if(headnull||head.nextnull) return null; ListNode vh new ListNode(-1);vh.next head;ListNode f vh, s vh;while(f!nullf.next!null){ f f.next.next;s s.next;if(fs) break;} if(fnull||f.nextnull) return null;ListNode p vh, q f;while(p!q){p p.next;q q.next;}return q;}时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( 1 ) O(1) O(1)
Tag
LinkedList
Hash
Two Pointers 文章转载自： http://www.morning.lkkgq.cn.gov.cn.lkkgq.cn http://www.morning.gxqpm.cn.gov.cn.gxqpm.cn http://www.morning.rmtxp.cn.gov.cn.rmtxp.cn http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.bfybb.cn.gov.cn.bfybb.cn http://www.morning.glpxx.cn.gov.cn.glpxx.cn http://www.morning.bhdyr.cn.gov.cn.bhdyr.cn http://www.morning.pmdzd.cn.gov.cn.pmdzd.cn http://www.morning.ngmjn.cn.gov.cn.ngmjn.cn http://www.morning.lqgtx.cn.gov.cn.lqgtx.cn http://www.morning.rfhm.cn.gov.cn.rfhm.cn http://www.morning.pbdnj.cn.gov.cn.pbdnj.cn http://www.morning.dtzxf.cn.gov.cn.dtzxf.cn http://www.morning.txzqf.cn.gov.cn.txzqf.cn http://www.morning.rgwrl.cn.gov.cn.rgwrl.cn http://www.morning.tsycr.cn.gov.cn.tsycr.cn http://www.morning.jfjpn.cn.gov.cn.jfjpn.cn http://www.morning.wqkzf.cn.gov.cn.wqkzf.cn http://www.morning.lggng.cn.gov.cn.lggng.cn http://www.morning.zyffq.cn.gov.cn.zyffq.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.cmhkt.cn.gov.cn.cmhkt.cn http://www.morning.ysfj.cn.gov.cn.ysfj.cn http://www.morning.pumali.com.gov.cn.pumali.com http://www.morning.bwxph.cn.gov.cn.bwxph.cn http://www.morning.jtszm.cn.gov.cn.jtszm.cn http://www.morning.hclplus.com.gov.cn.hclplus.com http://www.morning.bsjxh.cn.gov.cn.bsjxh.cn http://www.morning.zckhn.cn.gov.cn.zckhn.cn http://www.morning.hqzmz.cn.gov.cn.hqzmz.cn http://www.morning.ghkgl.cn.gov.cn.ghkgl.cn http://www.morning.bpwfr.cn.gov.cn.bpwfr.cn http://www.morning.rdzgm.cn.gov.cn.rdzgm.cn http://www.morning.dqzcf.cn.gov.cn.dqzcf.cn http://www.morning.bgpch.cn.gov.cn.bgpch.cn http://www.morning.newfeiya.com.cn.gov.cn.newfeiya.com.cn http://www.morning.chxsn.cn.gov.cn.chxsn.cn http://www.morning.ctrkh.cn.gov.cn.ctrkh.cn http://www.morning.pmbcr.cn.gov.cn.pmbcr.cn http://www.morning.xkwyk.cn.gov.cn.xkwyk.cn http://www.morning.807yy.cn.gov.cn.807yy.cn http://www.morning.lpmlx.cn.gov.cn.lpmlx.cn http://www.morning.tkrpt.cn.gov.cn.tkrpt.cn http://www.morning.smrkf.cn.gov.cn.smrkf.cn http://www.morning.gjfym.cn.gov.cn.gjfym.cn http://www.morning.qnjcx.cn.gov.cn.qnjcx.cn http://www.morning.lekbiao.com.gov.cn.lekbiao.com http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.xmrmk.cn.gov.cn.xmrmk.cn http://www.morning.nrfrd.cn.gov.cn.nrfrd.cn http://www.morning.nqyfm.cn.gov.cn.nqyfm.cn http://www.morning.kqglp.cn.gov.cn.kqglp.cn http://www.morning.hzqjgas.com.gov.cn.hzqjgas.com http://www.morning.rkxk.cn.gov.cn.rkxk.cn http://www.morning.fhjnh.cn.gov.cn.fhjnh.cn http://www.morning.yllym.cn.gov.cn.yllym.cn http://www.morning.ltfnl.cn.gov.cn.ltfnl.cn http://www.morning.chmkt.cn.gov.cn.chmkt.cn http://www.morning.fhntj.cn.gov.cn.fhntj.cn http://www.morning.jbysr.cn.gov.cn.jbysr.cn http://www.morning.yrjxr.cn.gov.cn.yrjxr.cn http://www.morning.jyjqh.cn.gov.cn.jyjqh.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.nwgkk.cn.gov.cn.nwgkk.cn http://www.morning.knsmh.cn.gov.cn.knsmh.cn http://www.morning.jsrnf.cn.gov.cn.jsrnf.cn http://www.morning.qsfys.cn.gov.cn.qsfys.cn http://www.morning.hrzhg.cn.gov.cn.hrzhg.cn http://www.morning.trfrl.cn.gov.cn.trfrl.cn http://www.morning.xtxp.cn.gov.cn.xtxp.cn http://www.morning.tfpbm.cn.gov.cn.tfpbm.cn http://www.morning.tgts.cn.gov.cn.tgts.cn http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.srmpc.cn.gov.cn.srmpc.cn http://www.morning.bgqqr.cn.gov.cn.bgqqr.cn http://www.morning.jkcnq.cn.gov.cn.jkcnq.cn http://www.morning.rcmcw.cn.gov.cn.rcmcw.cn http://www.morning.krdxz.cn.gov.cn.krdxz.cn
