本文共 2400 字，大约阅读时间需要 8 分钟。

package SwordOffer;import java.util.Stack;/*** @Description: 题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。* @Param:* @return:* @Author: lvhong* @Date:* @E-mail lvhong282@163.com*/public class lab23easy {  class ListNode {     int val;     ListNode next = null;     ListNode(int val) {         this.val = val;     } }//1 2 3 4 5 4//1 2 3 4 5 5//1 3 5 5 5 5////1 2 3 4 5 3//1 2 3 4 5 3 4//1 3 5 4 3 5 4////1 2 3 4 5 2//1 2 3 4 5 2 3 4 5//1 3 5 3 5 3 5 3 5////1 2 3 4 5 1//1 2 3 4 5 1 2 3 4 5 1//1 3 5 2 4 1 3 5 2 4 1    //求有环单链表的环长//在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。//设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：//　　　　环长=2*len-len    //求有环单链表的环连接点位置//　　第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。//　　　　第一次相遇时，slow走的长度 S = LenA + x;//　　　　第一次相遇时，fast走的长度 2S = LenA + n*R + x;//　　　　所以可以知道，LenA + x =  n*R;　　LenA = n*R -x;    //求有环单链表的链表长// 　　上述中求出了环的长度；求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。        public ListNode EntryNodeOfLoop(ListNode pHead) {            if (pHead == null || pHead.next == null) {                return null;            }            ListNode meetingNode = meetingNode(pHead);            if (meetingNode == null) {                return null;            }            // 得到环中节点的数目            ListNode cur = meetingNode.next;            int nodesInLoop = 1;            while (cur != meetingNode) {                nodesInLoop++;                cur = cur.next;            }            ListNode behind = cur = pHead;            // 先移动cur，次数为环中节点的数目            while (nodesInLoop-- > 0) {                cur = cur.next;            }            // 再移动behind和cur，相遇时即为入口节点            while (behind != cur) {                behind = behind.next;                cur = cur.next;            }            return behind;        }        private ListNode meetingNode(ListNode pHead) {            // 在链表中存在环时找到一快一慢两个指针相遇的节点，无环返回null            ListNode cur = pHead.next.next, behind = pHead;            while (cur != null) {                if (cur == behind) {                    return cur;                }                if (cur.next != null) {                    cur = cur.next.next;                } else {                    return null;                }                behind = behind.next;            }            return null;        }    }