题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
练习地址
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
参考答案
/*
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 || 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;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
