【链表6】链表中环的入口结点

题目描述

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

/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null)
            return null;
        
       ListNode slowNode=pHead;
       ListNode fastNode=slowNode.next;

        ListNode entryNode = null;//环中结点
       //1 双指针，先获取环中任一结点
       while(slowNode != null && fastNode!= null){
            if(fastNode.val == slowNode.val){
                entryNode = fastNode;
                break;
            }
            fastNode = fastNode.next;
            slowNode = slowNode.next;
           if(fastNode != null)
              fastNode=fastNode.next;
        }
        
        //判断此结点是否存在，不存在即不存在环
        if(entryNode == null)
            return null;
        
        //2 获取环的长度
        int lenOfCircleListNode =1;
        ListNode indexNode1 =entryNode.next;
        while(indexNode1 != entryNode){
            lenOfCircleListNode++;
            indexNode1 = indexNode1.next;
        }
        
        //3 双指针：让快指针先走（环长度）的步数，再两个指针一起走
        //直到碰到第一个相同的数即为环的入口结点
        
        //快指针
        indexNode1 = pHead;
        for(int i=0;i<lenOfCircleListNode;i++){
            indexNode1 = indexNode1.next;
        }
        //慢指针
        ListNode indexNode2 = pHead;
       while( indexNode2 != null){
            if(indexNode1.val == indexNode2.val){
                return indexNode1;//返回入口节点
            }
            indexNode2 = indexNode2.next;
            indexNode1 = indexNode1.next;
        }
        return indexNode2;
        
        
        
    }
}

还有一种更加简便的方法：利用set特性

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;


public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        Set<Integer> set = new HashSet<>();
        //环的特点与集合的特性：环的入口结点即为遍历环时遇到的重复的结点
        //而set集合不能添加重复结点.
        //当添加重复结点时，set.add返回false，此时中断while循环，此时的结点phead即为环的入口节点
        while(pHead != null && set.add(pHead.val)){
            pHead = pHead.next;
        }
        return pHead;
    }
}