一、题目内容

二、题解

解法1：

思路

a+x = nr = (n-1)r + r= (n-1)r + L - a
a = (n-1)r + L-a-x
L-a-x = 相遇到环入口

代码

public class Solution {
    /**
     * a+x = nr = (n-1)*r + r= (n-1)*r + L - a
     * a = (n-1)r + L-a-x
     * L-a-x = 相遇到环入口
     *
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //相遇
            if (fast == slow) {
                ListNode slow2 = pHead;
                while (slow2 != slow) {
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

解法2：

思路

在相遇点断开，就变成了求两个链表相交节点

代码

public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode pHead2 = slow.next;
                slow.next = null;
                ListNode temp1 = pHead, temp2 = pHead2;
                while (temp1 != temp2) {
                    temp1 = temp1 == null ? pHead2 : temp1.next;
                    temp2 = temp2 == null ? pHead : temp2.next;
                }
                return temp1;
            }
        }
        return null;
    }