FastAndSlowPointer

题目描述[原题描述][https://www.acwing.com/problem/content/description/86/]

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

算法描述

定义两个指针一个步长为2，一个步长为1，找到第一次相遇的节点，再在头节点定义一个节点与刚刚会和的节点一起以步长为1开始走，知道两个节点相遇，这个节点就是相遇点；

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head==NULL||head->next==NULL)return NULL;
        auto first = head,second = head;
        while(first&&second){
            first  = first->next;
            if(second->next->next==NULL)return NULL;
            second = second->next->next;
            if(first==second)break;
        }
        
        first = head;
        while(first!=second){
            first=first->next;
            second=second->next;
        }
        
        return first;
    }
};

Java代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode entryNodeOfLoop(ListNode head) {
        if(head==null)return null;
        ListNode first=head,second=head;
        while(second!=null&&first!=null){
            first=first.next;
            if(second.next.next==null)return null;
            second=second.next.next;
            if(first==second)break;
        }
        second=head;
        while(second!=first){
            second=second.next;
            first=first.next;
        }
        return first;
    }
}