【leetcode.141&142】環形連結清單及拓展

                                              環形連結清單及拓展

一、要求

給定一個連結清單，判斷連結清單中是否有環。

進階：

你能否不使用額外空間解決此題？

節點類：

class ListNode {
        public int val;
        public ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }      

二、解法

（1）使用額外空間來判斷連結清單中是否有環

思路：周遊整個連結清單，将每一次周遊的節點存入Set中，利用Set存入相同元素傳回false的特性，判斷連結清單中是否有環。

public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            boolean result = set.add(head);
            if (!result) {
                return true;
            }
            head = head.next;
        }
        return false;
    }      

由于周遊，導緻時間複雜度為O(n)，由于使用了Set集合，空間複雜度為O(n)。

（2）使用快慢指針。

思路：快慢指針都從頭節點開始，快指針一次走兩步，慢指針一次，如果慢指針能夠追趕上快指針，則證明連結清單中有環。

public boolean hasCylce2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //如果慢指針追趕上快指針的話，則說明有環
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }      

三、拓展

拓展問題一：

如果連結清單有環，找出環的入口節點。

思路：快慢指針的相遇點到環入口的距離等于頭節點到環入口的距離，那麼在頭節點和相遇點各設一個相同步伐的指針，他們相遇的那個節點就是環入口。

public ListNode getEntrance(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isCycle = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //如果慢指針追趕上快指針的話，則說明有環
            if (fast == slow) {
                isCycle = true;
                break;
            }
        }

        if (isCycle) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;
    }      

拓展問題二：

public int getCylceLength(ListNode head) {
        int length = 0;
        ListNode cycleNode = getEntrance(head);
        if (cycleNode != null) {
            ListNode temp = cycleNode;
            while (true) {
                temp = temp.next;
                length++;
                if (temp == cycleNode) {
                    break;
                }
            }
        }
        return length;
    }