链表中环的入口节点

题目描述

一个链表中包含环,请找出该链表的环的入口节点。

分析

两种思路

思路一:创建一个set,依次往set里添加节点。第二次到环的入口节点时,由于重复了,无法添加成功,返回该节点。

思路二:两个指针。具体分析见代码注释。

代码:

用HashSet(取巧)

import java.util.*;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if (pHead == null)
return null;
ListNode p = pHead;
HashSet<ListNode> set = new HashSet<ListNode>();
while (p != null){
if (!set.add(p))
return p;
p = p.next;
}
return null;
}
}

两个指针(巧妙)

public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if (pHead == null || pHead.next == null) return null;
ListNode p1 = pHead, p2 = pHead;
while (p2 != null){
p1 = p1.next; //p1每次走一步
p2 = p2.next.next; //p2每次走两步
if (p1 == p2){ //第一次相遇,此时p2刚好比p1多走一个环的长度,又因为p2走的距离是p1的两倍,所以p1刚好走了一个环的距离
p1 = pHead; //p1回到头节点,p2不动。此时p1,p2刚好相差一个环的距离
while (p1 != p2){ //p1、p2每次都只走一步,下次相遇必定在环的入口节点
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :