【算法】环形链表 - 遍历/双指针

题目

给定一个链表，判断链表中是否有环，并返回结果。

原理

遍历

声明一个Set，遍历链表放入Set，如果放入失败，说明有环。

双指针

声明一个快指针和一个慢指针，快指针每次移动两步，慢指针移动一步，如果两指针相等则说明有环。

代码

遍历

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);
        listNode5.next = listNode2;
        System.out.println(hasCircleByFor(listNode1));
    }

    private static boolean hasCircleByFor(ListNode head) {
        Set<ListNode> nodeSet = new HashSet<>();
        while (head != null) {
            if (!nodeSet.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

双指针

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);
        listNode5.next = listNode2;
        System.out.println(hasCircleByTwoPointer(listNode1));
    }

    private static boolean hasCircleByTwoPointer(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }