链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解法1:

新建一个HashSet,遍历链表,每次尝试添加当前遍历的节点到HashSet,如果添加失败,则代表HashSet中已经包含该节点,此时的节点即为环的入口点.

代码如下:

  public static ListNode solution1(ListNode pHead) {
        ListNode node = pHead;
        HashSet<ListNode> set = new HashSet<>();
        while (node != null) {
            if (!set.add(node)) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

因为额外申请了内存,所以空间复杂度为O(n),时间复杂度为O(n)

解法2:

1. 首先判断链表中是否有环,可以定义两个指针,一个每次走一步,一个每次走两步,如果快指针走到链表尾部时,两个指针没有相遇,则代表无环,否则说明又环.
2. 确定环中节点的个数n.
3. 将两个指针移动到链头,一个先走n步,然后两个指针一起走,如果两个指针相遇,则相遇点就是环的入口点.

代码如下:

 public static ListNode solution2(ListNode pHead) {

        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                fast = pHead;
                while (slow != fast) {
                    fast = fast.next;
                    slow = slow.next;
                }

                return slow;
            }
        }
        return null;
    }

此处并没有严格按照1,2,3的步骤,因为第一次两个指针相遇的节点处,就是3中先走的n步,假设slow指针走了x步,那么第一次相遇的时候,fast走了2x步,如果环中有n个节点,则fast比slow多走了n步,即2x-n=x,则x=n,所以两个指针第一次相遇的节点就是一个指针从链表头走了环中节点个数n步的位置.

这里并没有额外申请控件,只是用了两个指针变量,所以空间复杂度为O(1),时间复杂度为O(n)

代码的正确性可以到牛客网进行验证

牛客网剑指offer