本题为剑指offer面试题56
牛客网测试地址：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
[编程题]链表中环的入口结点 热度指数：35630时间限制：1秒空间限制：32768K 算法知识视频讲解 一个链表中包含环，请找出该链表的环的入口结点。Java代码：
package go.jacob.day606; /* * 思路：如果链表中有环，那么闲获取环中节点个数n，设置两个指针指向pHead * 快指针向前移动n次，然后进行循环，快慢指针同时向后移动，直到指向的节点相同，即环入口节点 * * 获取环中节点个数：设置两个指针：p1和p2.p1一次移动一次，p2一次移动两次 * 当p2等于p1，说明存在环。返回该节点 * 通过该节点很容易能获得环中节点个数 */ public class Demo1 { public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null) return null; ListNode meetingNode = MeetingNode(pHead); // 如果不存在环 if (meetingNode == null) return null; // 获取环中元素个数 ListNode tmpNode = meetingNode.next; int count = 1; while (tmpNode != meetingNode) { tmpNode = tmpNode.next; count++; } // 设置快慢指针 ListNode pSlow = pHead, pFast = pHead; for (int i = 0; i < count; i++) { pFast = pFast.next; } while (pSlow != pFast) { pSlow = pSlow.next; pFast = pFast.next; } return pSlow; } // 获取环中的任意一个节点 private ListNode MeetingNode(ListNode pHead) { if (pHead == null) return null; ListNode pSlow = pHead.next; ListNode pFast = pHead.next; if (pFast == null) return null; pFast = pFast.next; while (pSlow != null && pFast != null) { if (pSlow == pFast) return pSlow; pSlow = pSlow.next; pFast = pFast.next; if (pFast != null) pFast = pFast.next; } return null; } class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } }
