问题
一个链表中包含环,请找出该链表的环的入口结点。
解决思路
第一步,找环中相汇点。分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。
第二步,找环的入口。接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。(还没怎么懂)
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
<?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ function EntryNodeOfLoop( $pHead ) { if ( $pHead == null || $pHead ->next == null) return null; $p1 = $pHead ; $p2 = $pHead ; while ( $p2 !=null && $p2 ->next!=null){ $p1 = $p1 ->next; $p2 = $p2 ->next->next; if ( $p1 == $p2 ){ $p2 = $pHead ; while ( $p1 != $p2 ){ $p1 = $p1 ->next; $p2 = $p2 ->next; } if ( $p1 == $p2 ) return $p1 ; } } return null; } |
原文链接:http://blog.csdn.net/acingdreamer/article/details/70039299
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容