分类
LeetCode

141. Linked List Cycle 「环形链表」

给定一个链表,判断其中是否有环。

为了表示链表中的环,我们使用一个整数 pos 来表示尾部节点指向节点的索引。如果 pos-1,表示链表中不存在环。

例一:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中存在环,尾部节点连接到了第二个节点。

例二:
输入: head = [1,2], pos = 0
输出: true
解释: 链表中存在环,尾部节点连接到了第一个节点。

例三:
输入: head = [1], pos = -1
输出: false
解释: 链表中不存在环。

/*
 * 141. Linked List Cycle
 * https://leetcode.com/problems/linked-list-cycle/
 * https://realneo.me/141-linked-list-cycle/
 */

public class HasCycle {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        HasCycle solution = new HasCycle();

        System.out.println(solution.hasCycle(head));

        node.next = head.next.next.next;

        System.out.println(solution.hasCycle(head));
    }

    private boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;

        //快慢法查找
        ListNode slow = head;
        ListNode fast = head.next;

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

        if (fast == null || fast.next == null)
            return false;

        return true;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注