题解 | #链表中环的入口结点#

import java.util.*;
/*
 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 slow = pHead;
        ListNode fast = pHead;
        boolean flag = false;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                flag = true;
                break;
            }
        }
        if(!flag) {
            return null;
        }
        ListNode pHead2 = slow.next;
        slow.next = null;
        ListNode p1 = pHead;
        ListNode p2 = pHead2;
        int length1 = 1;
        int length2 = 1;
        while(p1.next != null) {
            p1 = p1.next;
            length1++;
        }
        p1 = pHead;
        while(p2.next != null) {
            p2 = p2.next;
            length2++;
        }
        p2 = pHead2;
        if(length1 > length2) {
            for(int i = 0; i < length1 - length2; i++) {
                p1 = p1.next;
            }
        }
        else if(length1 < length2){
            for(int i = 0; i < length2 - length1; i++) {
                p2 = p2.next;
            }
        }
        while(p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

总体思路：将带环链表的环部分断掉使链表成为两个具有公共部分的链表，转化为求公共部分入口

1.判断是否有环，若有则继续

2.确定快慢指针相遇的节点，用工作指针指向该结点的后继使其为第二个链表的头，再断掉该节点的指针，使其成为两个链表的尾结点

3.求出两个链表的长度之差，设两个指向两个表头的指针，较长的链表的工作指针从头开始先走差值的长度，然后两个链表的同步走，相遇的首个结点即为所求