剑指offer_链表中环的入口节点

桃扇骨 2022-06-09 03:07 195阅读 0赞

/*
    一个链表中包含环，请找出该链表的环的入口结点。
    已知的关于环的知识点：
    环在末尾
    用快慢指针可以判断是否包含环，快慢指针能遇见则包含
    
    如果一个结点不在环上但它的下一个结点在环上，则下一个结点是入口节点
    如何判断一个结点在不在环上?
    结点在环上的话好判断，因为走一圈还可以再遇到，遇到就返回true
    不在环上的话，怎么判断？
    在环上走一圈没遇到就结束，认为不在环上，如何判断已经走了一圈？
    先找到一个环上的元素，如果遇到该元素两次则证明已经在环上走一圈了
    O(n^2)时间复杂度太高
    
    搞这么复杂，还不如直接用一个辅助数组保存遍历过的结点，第一次遇到之前遍历过的结点则为环的入口，也是O(n^2)
    
    剑指offer思路：
    快指针比慢指针先走p步，p为环上元素个数，然后两个一起走，等快慢指针相遇的结点就是入口
    如何求p，先找到一个环上的元素，顺着环走一圈，统计元素个数，当再次遇到该元素，则统计结束
    
    */
      class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    
    class  EntryNodeOfLoop
    {
    	public static ListNode entryNodeOfLoop(ListNode pHead)
        {
            if (pHead==null)
            {
    			return null;
            }
    
    		//寻找环上的一个结点
    		ListNode fast=pHead.next;
    		ListNode slow=pHead;
    		while(fast!=null&&fast!=slow)
    		{
    			slow=slow.next;
    			fast=fast.next;
    			if (fast!=null)
    			{
    				fast=fast.next;
    			}
    		}
    		
    		ListNode temp=pHead;
    		while (temp.next!=null)
    		{
    			//一个结点不在环上但它的下一个结点在环上
    			if (!isInLoop(temp,fast)&&isInLoop(temp.next,fast))
    			{
    				return temp.next;
    			}
    			temp=temp.next;
    		}
    
    		return null;
        }
    
    	public static boolean isInLoop(ListNode node, ListNode nodeInLoop)
        {
    		ListNode temp=node;
    		int count=0;
    		while (temp.next!=node)
    		{
    			//第一次遇到环上的结点
    			if (temp.next==nodeInLoop)
    			{
    				count++;
    			}
    			//遇到环上的结点不止一次，证明环遍历结束
    			if (count>1)
    			{
    				return false;
    			}
    			temp=temp.next;
    		}
    		return true;
    	}
    
    	public static ListNode entryNodeOfLoop2(ListNode pHead)
        {
            if (pHead==null)
            {
    			return null;
            }
    
    		//寻找环上的一个结点
    		ListNode fast=pHead.next;
    		ListNode slow=pHead;
    		while(fast!=null&&fast!=slow)
    		{
    			slow=slow.next;
    			fast=fast.next;
    			if (fast!=null)
    			{
    				fast=fast.next;
    			}
    		}
    		
    		//统计环上结点个数
    		int count=1;
    		ListNode temp=fast;
    		while (temp!=null&&temp.next!=fast)
    		{
    			count++;
    			temp=temp.next;
    		}
    		
    		//fast先走count步
    		fast=pHead;
    		int i=0;
    		while (i<count&&fast!=null)
    		{
    			fast=fast.next;
    			i++;
    		}
    		
    		//fast和slow同时走
    		slow=pHead;
    		while (fast!=null&&slow!=null)
    		{
    			if (fast==slow)
    			{
    				return fast;
    			}
    			fast=fast.next;
    			slow=slow.next;
    		}
    
    		return null;
        }
    
    	public static void main(String[] args) 
    	{
    		ListNode head=new ListNode(0);
    		ListNode node1=new ListNode(1);
    		ListNode node2=new ListNode(2);
    		ListNode node3=new ListNode(3);
    		ListNode node4=new ListNode(4);
    		ListNode node5=new ListNode(5);
    
    		head.next=node1;
    		node1.next=node2;
    		node2.next=node3;
    		node3.next=node4;
    		node4.next=node5;
    		node5.next=node2;
    		System.out.println(entryNodeOfLoop2(head).val);
    	}
    }