题解 | #链表中环的入口结点#

/*
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode (int x)
    {
        val = x;
    }
}*/
using System.Collections.Generic;
class Solution
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {   
        // write code here
        ListNode LoopEntrance = new ListNode(0);
        ListNode LoopEntrance_next = pHead;
        LoopEntrance.next = LoopEntrance_next;
        List<ListNode> next_pointer = new List<ListNode>();
        next_pointer.Add(pHead);//为了应对单链长度为0的情况，特地将LoopEntrance指向pHead的地址加入到下一个节点指针的集合里，否则环的入口处不存在指向该处的指针，造成循环继续，返回的节点是入口节点的下一个节点
        do//一个无限循环，持续寻找
        {
            if(LoopEntrance_next.next == null)//如果是单链后什么都没有，返回null。只要环成型，链表里一定不会存在指向null的指针
            {
                return null;
            }
            if(next_pointer.Count != 1)//该条件判断成立意味着指针集合中有了新添加的元素
            {
                foreach(ListNode l in next_pointer)//将当前节点的指向下一个节点的指针与指针集合中的元素进行对比
                {
                    if(l == LoopEntrance_next.next)//当前节点指向下一个节点的指针已经出现过时
                    {
                        if(l == pHead)//如果这个指针恰好是输入的头节点，说明链表仅包含一个环，而头节点就是入口
                        {
                            return pHead;
                        }
                        else//否则当前节点指向的下一个节点就是环的入口
                        {
                            return LoopEntrance_next.next;
                        }
                    }
                }
            }
            next_pointer.Add(LoopEntrance_next.next);//当前节点指向下一个节点的指针未出现过，则加入指针集合中
            ListNode buffer = LoopEntrance_next.next;
            if(buffer == null)//只要发现了空节点，环结构就一定不存在
            {
                return null;
            }
            else
            {
                if(buffer == LoopEntrance_next)//一个节点有可能指向自己成环，这个判断是为了识别这种情况。自我成环时入口即是自身
                {
                    return buffer;
                }
                LoopEntrance_next = LoopEntrance_next.next;//经过前面的步骤未发现环入口，移位，查看下一个节点
            }
        }while(true);
    }
}