iT邦幫忙

DAY 30
1

連續30天,挑戰演算法系列 第 30

[Day30] 30 天挑戰演算法 - 判斷循環的LinkedList

喔耶!終於最後一天了!
今天就來點簡單的題目緩和緩和吧!!

題目來源Leet Code Online Judge

問題:
給予一個 LinkedList ,請判斷是否為循環的 LinkedList。
註:不能額外宣告記憶體空間來儲存 LinkedList
題目定義的 ListNode 為

public class ListNode {
    ListNode next;
    int val;
    public ListNode(int value) {
        this.val = value;
    }
}

例子
給予一個 LinkedList 如下圖,為循環的 LinkedList

給予一個 LinkedList 如下圖,為非循環的 LinkedList

想法
如果說不能額外宣告記憶體空間來解這題,那麼我們就需要用兩個指標來完成。
讓這兩個指標一前一後,一個一次走一個節點、另一個指標一次走兩個節點,倘若題目給予的 LinkedList 是循環的 LinkedList,則這兩個指標一定會碰面(指向同一個節點的意思),就可得知這個 LinkedList 為循環的 LinkedList。若這個 LinkedList 為非循環的,那麼走在前面的那個指標一定會先遇到終點(null),那麼就可以知道這個 LinkedList 為非循環的!
當然,在一開始還是要先判斷題目給予的 LinkedList 是否為空的。

下面的程式碼中,我們用 node1, node2 來訪問這個 LinkedList, 並且讓 node1 一次訪問兩個,如果此 LinkedList 為循環的,則 node1 就為有機會跟 node2 指向同一個節點,反之則不會。

public void isCycleLinkedList(ListNode head) {
    if (head == null)
        return false;
        
    ListNode node1 = head;
    ListNode node2 = head;
    while(node1 != null) {
        if (node1.next == null)
            return false;
        node1 = node1.next;
        
        if (node1 == node2)
            return true;
        node1 = node1.next;
        node2 = node2.next;
    }
    return false;
}

一定會有人想說,為什麼不把 head 先保留下來,然後一直訪問下去,直到某個節點等於 head 就是循環,反之,一定會遇到 null 呢?一開始我也是這麼想的,可是就如同我給的範例,因為題目並沒有說循環一定是從頭循環,所已有可能在此 LinkedList 中的某一個節點循環,所以不能把 head 保留下來做判斷!

那這個作法就是時間複雜度比較高,但空間複雜度是低的!如果想要降低時間複雜度,我的想法就是另外宣告一個記憶體空間來存放此 LinkedList 就可以把時間複雜度降到 O(N) , 可是,空間複雜度就會提升!置於要怎麼取捨就得看應用囉!至少這題,題目規定說不能額外宣告記憶體空間。所以我就這樣做了!不過我想,應該會有更好的作法吧!只是我目前還沒想到!

最後,30天達到了!YA~ 感覺輕鬆多了!


上一篇
[Day29] 30 天挑戰演算法 - 合併兩個已排序的 List
系列文
連續30天,挑戰演算法30
0
小財神
iT邦好手 1 級 ‧ 2014-10-30 18:10:42

哇~第30天也完全不含糊,讚!

恭喜!賀喜!

0
wooly
iT邦新手 5 級 ‧ 2014-12-05 14:24:02

以前我也只記得你上面寫的方法,有人叫它是runner技巧,也有人叫它是two pointers技巧,一直到幾個月我被考試時問了 reverse list的做法,也才發現用 reverse list的做法也能做為這一題的答案之一.

0
wooly
iT邦新手 5 級 ‧ 2014-12-05 14:24:08

以前我也只記得你上面寫的方法,有人叫它是runner技巧,也有人叫它是two pointers技巧,一直到幾個月我被考試時問了 reverse list的做法,也才發現用 reverse list的做法也能做為這一題的答案之一.

我要留言

立即登入留言