题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead){            }}

解法一

遍历链表的时候，用一个容器list依次装入链表的节点，如果发现有重复的节点，那么就是链表的环的入口节点

import java.util.ArrayList;public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead){        ArrayList<ListNode> list = new ArrayList<>();        while (!list.contains(pHead) && pHead != null){            list.add(pHead);            pHead = pHead.next;        }        return pHead;    }}

时间复杂度：O(n^2)

解法二

采用双指针的方法（这个方法还可以用来判断链表中有没有环），一个快指针一个慢指针，快指针一次走两步，慢指针一次走一步，如果链表中有环，那么两个指针一定就可以相遇，并且相遇的地方，一定在环的某处

设相遇的地方距环的入口点一边有a个节点，一边有b个节点，链表除环以外有x个节点，环中一共有c个节点（c=a+b）

那么可以得到如下关系式，用b = c -a表示

][1]

 public ListNode EntryNodeOfLoop(ListNode pHead){        if(pHead == null || pHead.next == null)return  null;        ListNode slow = pHead.next;        ListNode fast = pHead.next.next;        while (slow != fast && pHead != null){            slow = slow.next;            fast = fast.next.next;        }        slow = pHead;        while(slow != fast){            slow = slow.next;            fast = fast.next;        }        return slow;    }

该方法的时间复杂度为O(n)

参考

《剑指offer》——链表中环的入口结点