mc做图的网站/宁波网站推广优化公司怎么样
一、题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
二、解题思路
1)定义两个指针均指向头结点,一个慢指针每次往后移动一步,一个快指针每次往后移动两步;
2)两者如果相遇,则一定相遇在环中。此时快指针移动2X,慢指针移动X,快指针比慢指针在环中多走一圈,所以2X-X=X等于环的长度,也就是慢指针走的长度即为环的长度。
3)将快指针重新指向头结点,此时,慢指针比快指针多走一个环的距离,两个指针均一步一步往后移动;
4)直至相遇时即为环的入口结点。
例如:环为3 -> 4 -> 5 -> 6 -> 3,慢指针每次往后移动一步,快指针移动两步
链表:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3
慢指针:1 -> 2 -> 3 -> 4 -> 5
快指针:1 -> 3 -> 5 -> 3 -> 5
相遇在5,此时慢指针移动4步,即为环的长度,快指针重新指向头结点,两个指针均一步一步往后移动
链表:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3
慢指针:5 -> 6 -> 3
快指针:1 -> 2 -> 3
相遇在3,即为环的入口结点
三、编程实现
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {if (pHead == null || pHead.next == null) {return null;}// 两个指针均指向头结点ListNode p1, p2;p1 = p2 = pHead;while (p2 != null && p2.next != null) {// p1每次往后移动一步p1 = p1.next;// p2每次往后移动两步p2 = p2.next.next;// 两者如果相遇,则一定相遇在环中if (p1 == p2) {// 将p2重新指向头结点p2 = pHead;while (p1 != p2) {// 两个指针均一步一步往后移动p1 = p1.next;p2 = p2.next;}// 两个指针相遇时即为环的入口结点return p1;}}return null;}
}