快慢指針問題的討論

又是一個非常常見的問題.

最近在緩慢的學習 leetcode 上面的習題. 看到了有些問題都和這個有點關係,就總結下來.

原始問題大家都很熟悉了.

141. Linked List Cycle I

給定鏈表,發現其中是否有環.n

暴力手段,就是保存所有自鏈表頭部節點開始的所有節點,然後一邊向後遍歷,一邊向前比較,如果沒有重複出現節點,那麼不存在環路;如果有重複出現的節點,那麼檢測到存在環路.

這種方式,因為需要保持已經遍歷過的節點,因此需要較多的存儲空間. 同時因為比較過程也比較複雜,時間複雜度也不好.

這個問題可以通過快慢指針很好的解決.

- 慢指針:每次迭代,向前移動一個節點 `pSlow = pSlow->next;`n- 快指針:每次迭代向前移動兩個節點 `pFast = pFast->next->next;`n

如果pFast或者pFast->next為NULL,則檢查到鏈表尾部,發現沒有存在環路; 如果發現 pFast == pSlow 則存在環路.

需要注意的一點是,當發現 pFast == pSlow 的時候,並不一定是鏈表出現環路位置的入口位置.

暴力手段之所以複雜,主要在於沒有充分利用題目的限定條件. 題目考慮是否出現環路的問題,如果出現環路,那麼必然會遍歷到已經遍歷過的節點.但是此時,並不需要第一次檢查到遍歷過的節點是,就立刻檢查出來. 而因為環路存在,後續被繼續遍歷的節點,實際上也會被再次檢查到.我們在之後的位置,檢查到環路也是可以的. 快慢指針的方案,就放棄了」在環路入口位置就檢查到環路存在」這一點,從而另闢蹊徑.

linkedListCycle.141.c

142. Linked List Cycle II

給定鏈表,如果存在環路,找到環路的入口位置;如果不存在環路,返回`NULL`n

很明顯,這個問題在141問題基礎上更進一步. 例如141的快慢指針方案,可以簡單快速的找到入口的存在.

假設存在環路, 環路部分節點個數為r, 從頭部到環路部分節點個數為l. 那麼到快慢指針相遇,慢指針走了s步,快指針走可2s步.因為快指針走的快,在環路上饒圈子,設饒了k圈,整圈之外又走了r0步.

則

s = l + r0n2s = l + kr + r0n=>n2(l + r0) = l + kr + r0nr0 = kr - ln

因此考慮如何找到環路的入口處,也就是尋找到消除r0的方式.所以消除r0的方式,就是再移動 l 步.因此將一個指針放回到鏈表入口head處,然後另一個指針繼續在環路上轉圈子,直到二者再次相遇,這個時候,就是環路的入口位置.

linkedListCycle.142.c

148. Sort List

排序一個鏈表.n

根據鏈表的特性,合併排序最為簡單,因為鏈表的合併過程,可以之間通過鏈表的指針過程進行,因此不需要數據的額外搬運過程.

如果鏈表當中沒有環路的話,使用快慢指針可以快速得到鏈表的中點位置. 當快指針走到鏈表的尾部的時候,慢指針剛好在鏈表的中點位置.

在合併排序一個鏈表的時候,就利用這個技巧可以定位到鏈表的中間位置,然後分別對前後各一半進行排序,然後再把二者合併起來.

sortList.148.c

234. Palindrome Linked List

檢查鏈表是否是迴文.n

同樣需要尋找鏈表的中間節點,需要選擇鏈表的中間節點,那麼就可以將鏈表的後半部分逆序,然後就變成鏈表的前半部分和(逆序後的)後半部分的比較問題.比較結束後,可以再次將後半部分逆序回去,從而保持鏈表不變.

一個小細節,就是鏈表的長度是奇數的時候,這個時候鏈表不能夠均分為兩部分,我們需要找的是鏈表的後中位點,因此需要pSlow向前再移動一次.

validPalindLinkedList.234.c

以上兩個小問題,僅僅是根據快慢指針需要鏈表的中間位置,非常簡單.

202. Happy Number

檢查一個數是否是happy number.nn對數字可以進行一種迭代,各位數字的平方和.反覆進行迭代,如果可以迭代到1,那麼因為1的平方和就是1,迭代就會停止,這個數字就是happy number,如果可以循環進行這種迭代,一直到無法迭代到1,那麼就不是happy number.n

比如:19就是happy number.因為

1 ^ 2 + 9 ^ 2 = 82n8 ^ 2 + 2 ^ 2 = 68n6 ^ 2 + 8 ^ 2 = 100n1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1n

顯然這個問題和快慢指針的問題,有一定的相似之處,都是檢查環路或者尾部的存在性的.

首先可以定義好迭代函數iter. 「快指針」迭代兩次,」慢指針」迭代一次,如果快指針迭代過程中可以達到1,則是happy number,如果」快指針」,」慢指針」二者相等(相遇),則說明可以循環進行,不是happy number.

因此可以看到這個問題和快慢指針問題是同構的.只是,對於鏈表環路檢查問題,迭代函數是->next,尾部節點是NULL;對於這個問題迭代函數是上述計算過程 iter 而已.尾部節點是1.

(x -> x->next, nil) <=> (iter, 1)n

happyNumber.202.c

287. find duplicate nums

已知數組中包含`n + 1`個元素,任意元素在`[1, n]`範圍內的整數.顯然根據抽屜原理,必然存在一個元素,在至少出現了兩次.找到這個重複出現的元素.nn需要注意:數字中重複出現的元素,也可能重複出現多次.n

暴力方案,直接對數組進行一個統計,最後直接可以找到重複出現的元素,這個方案需要O(n)的存儲空間.時間複雜度也是O(n).或者直接進行雙重循環,則時間複雜度為O(n^2),不需要額外的存儲空間.如果可以限定出現元素的次數,還有可能通過位運算的技巧解決.但是這裡重複出現的元素的出現次數是不定的.其他沒有出現的元素(如果存在的話),也是不定的.因此也無法通過位運算解決.

學習過完全二叉樹的數組表示的,之道數組的下標(index),其實就是一種指針.而在這個問題中數組的下標取值範圍為[0, n],所以這個數組就是一個定義域為[0, n],值域為[1, n]的函數,記這個函數為A,並且A也是可以反覆迭代的.重複出現的元素,則意味著A(a) = A(b) = c,其中a < b. 比如數組:

[1, 2, 4, 2, 3]n下標為n 0, 1, 2, 3, 4n

這個數組表示的函數中A(1) = A(3) = 2, 則這個數組的迭代過程(設從0開始):

0 -> 1 -> {2 -> 4 -> 3} -> 2 -> 4 -> 3 -> ...n

可以看到2->4->3出現了一個環路.而問題就是尋找這個環路的入口節點.這也是鏈表環路的同構問題可以,完全可以通過快慢指針的技巧完成.

findDup.287.c

----

同步更新於github博客