链表中环的入口结点

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) {
        Set<ListNode> set = new HashSet<>();

        while (pHead != null) {
            if (!set.add(pHead)) {
                return pHead;
            }
            pHead = pHead.next;
        }
        
        return null;
    }
}

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) {
        ListNode cycle = pHead.next;
        return EntryNodeOfLoop1(pHead, cycle, 1);
    }

    public static ListNode EntryNodeOfLoop1(ListNode pHead, ListNode cycleNode,
                                            int k) {
        if (pHead == null || cycleNode == null) {
            return null;
        }
        int i = 1;
        ListNode cycle = null;
        ListNode current = pHead;
        while (i <= k && current.next != null) {
            if (current == cycleNode) {
                cycle = current;
                break;
            }
            current = current.next;
            i++;
        }
        if (cycle == null) {
            cycle = EntryNodeOfLoop1(pHead, cycleNode.next, k + 1);
        }
        return cycle;
    }
}

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) {
        // 左程云老师讲过这道题，采用快慢指针，快指针一次走两个结点，慢指针一次走一个结点，若二者能相遇，则有环，否则无环
        // 若有环，在快慢指针相遇之后，令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.先判断链表为空的情况
        if (pHead == null) {
            return null;
        }

        // 2.确定链表不为空
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean hasCycle = false;
        // 注意！这里不能用while而应该用do while
        // 因为fast和slow初始化就是相同的，用while会直接跳出循环
        do {
            // 3.如果链表是无环的，那么fast一定先走到null，直接return false即可
            if (fast.next == null || fast.next.next == null) {
                // 这里一定不会报空指针异常，因为先判断fast.next == null，若满足，则直接return false，不会继续判断后面
                return null;
            }
            // 4.快指针一次走两个结点，慢指针一次走一个结点
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);

        // 5.若因为fast == slow而结束循环，说明fast和slow二者相遇了，说明链表有环
        // 若有环，则令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点
        fast = pHead;
        // 注意！这里不能用do while而应该用while
        // 假如成环结点就是pHead，用do while会错过一次判断
        while (fast != slow) {
            // 6.快指针降速为一次走一个结点，慢指针依然是一次走一个结点
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead) {

    SetListNode> set = new HashSet();

    while(pHead != null){

        if(!set.add(pHead)){

            break;

        }

        pHead = pHead.next;

    }

    return pHead;

}

}

public class Solution {

    //链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度
    //判断有没有环，返回相遇的地方
    public ListNode hasCycle(ListNode head) {
        //先判断链表为空的情况
        if (head == null)
            return null;
        //快慢双指针
        ListNode fast = head;
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while (fast != null && fast.next != null) {
            //快指针移动两步
            fast = fast.next.next;
            //慢指针移动一步
            slow = slow.next;
            //相遇则有环，返回相遇的位置 
            if (fast == slow)
                return slow;
        }
        //到末尾说明没有环，返回null
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);
        //没有环
        if (slow == null)
            return null;
        //快指针回到表头
        ListNode fast = pHead;
        //再次相遇即是环入口
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

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) {
        
        while(pHead != null){
            if(pHead.val < 0){
                pHead.val = pHead.val + Integer.MAX_VALUE;
                return pHead; 
            }else{
                pHead.val = pHead.val - Integer.MAX_VALUE;
                pHead = pHead.next;
            }
        }
        return null;

    }
}

思路：走过更新数据为负数，当值为负数表示有环，把数还原回来，在这里使用了int最大值