55. 链表中环的入口结点
题目描述
给一个链表, 若其中包含环, 请找出该链表的环的入口结点, 否则, 输出 null
法一:(我没看懂)
思路:
快慢指针, 快指针一次走两步, 慢指针一次走一步, 相遇后, 快指针回到头结点, 以一次一步的速度和慢指针一起走, 再次相遇的结点即是环的入口点
- public class Solution {
- public ListNode EntryNodeOfLoop(ListNode pHead)
- {
- if(pHead == null || pHead.next == null || pHead.next.next == null)
- return null;
- ListNode fast = pHead.next.next, low = pHead.next;
- while(fast != low){
- if(fast.next == null || low == null)
- return null;
- fast = fast.next.next;
- low = low.next;
- }
- fast = pHead;
- while(fast != low){
- fast = fast.next;
- low = low.next;
- }
- return fast;
- }
- }
法二:
思路: 把所有结点存入一个 ArrayList 中, 第一个重复的结点就是入口结点, 如果没有重复结点, 则无环
- import java.util.ArrayList;
- public class Solution {
- public ListNode EntryNodeOfLoop(ListNode pHead)
- {
- // 如果链表只有一个结点或者没有结点则直接返回空
- if(pHead == null)
- return null;
- ArrayList<ListNode> list = new ArrayList<ListNode>();
- list.add(pHead);
- ListNode p = pHead.next;
- while(p != null){
- if(list.contains(p)){
- return p;
- }
- list.add(p);
- p = p.next;
- }
- return null;
- }
- }
来源: http://www.bubuko.com/infodetail-3447504.html