【Leetcode】142. 环形链表 II

题目描述

// 142. 环形链表 II

// 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

// 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（
// 索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于
// 标识环的情况，并不会作为参数传递到函数中。

// 说明：不允许修改给定的链表。
// 进阶：
// 你是否可以使用 O(1) 空间解决此题？

题解

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 
 
// HashSet法
// 如果借助hashset就太简单了。直接指针cur一边移动一边把结点存入set，
// 存不进去说明已经遇到重复结点，第一个遇到的重复结点就是环的入口。
// 返回当前遍历节点即可。如果cur遇到null，直接返回null

// 执行用时：4 ms, 在所有 Java 提交中击败了21.00%的用户
// 内存消耗：39.7 MB, 在所有 Java 提交中击败了5.09%的用户
import java.util.HashSet;
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        HashSet<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (!set.add(cur))
                return cur;
            cur = cur.next;
        }
        return null;
    }
}

// 双指针法
// 定义intersection函数：
// 先快慢针判断是否有环，有环，快针慢针第一次相遇地点被记录，无环，返回null。
// 这个地方跟 141. 环形链表 很像，又有不同，不能用不同起点的快慢针法，必须要
// 同起点的快慢针法。
// 
// 快针慢针第一次相遇地点记录为inLoop，之后从头再构造一个指针outLoop，
// inLoop从第一次相遇地点开始走，outLoop从头开始走，两指针相遇的地点
// 一定是环形链表的环入口。返回该相遇点即可。
// 
// 执行用时：1 ms, 在所有 Java 提交中击败了32.80%的用户
// 内存消耗：38.6 MB, 在所有 Java 提交中击败了51.78%的用户
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode inLoop = intersection(head);
        if (inLoop == null)
            return null;
		
        ListNode outLoop = head;
        while (inLoop != outLoop) {
            inLoop = inLoop.next;
            outLoop = outLoop.next;
        }
        return inLoop;
    }

    public ListNode intersection(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode pre = head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            cur = cur.next.next;
            pre = pre.next;
            if (cur == pre)
                return cur;
        }
        return null;
    }
}