指針和演算法

㈠ 判斷單鏈表有沒有環的演算法中，至少需要幾個指針

演算法的思想是設定兩個指針p,
q，其中p每次向前移動一步，q每次向前移動兩步。那麼如果單鏈表存在環，則p和q相遇；否則q將首先遇到null。
這里主要理解一個問題，就是為什麼當單鏈表存在環時，p和q一定會相遇呢？
假定單鏈表的長度為n，並且該單鏈表是環狀的，那麼第i次迭代時，p指向元素i
mod
n，q指向2i
mod
n。因此當i≡2i(mod
n)時，p與q相遇。而i≡2i(mod
n)
=>
(2i
-
i)
mod
n
=
0
=>
i
mod
n
=
0
=>
當i=n時，p與q相遇。這里一個簡單的理解是，p和q同時在操場跑步，其中q的速度是p的兩倍，當他們兩個同時出發時，p跑一圈到達起點，而q此時也剛
好跑完兩圈到達起點。
那麼當p與q起點不同呢？假定第i次迭代時p指向元素i
mod
n，q指向k+2i
mod
n，其中0<k<n。那麼i≡(2i+k)(mod
n)
=>
(i+k)
mod
n
=
0
=>
當i=n-k時，p與q相遇。
解決方案：
推廣：
1.
如果兩個指針的速度不一樣，比如p，q，(
0<p<q)二者滿足什麼樣的關系，可以使得兩者肯定交與一個節點？

Sp(i)
=
pi

Sq(i)
=
k
+
qi

如果兩個要相交於一個節點，則
Sp(i)
=
Sq(i)
=>
(pi)
mod
n
=
(
k+
qi
)
mod
n
=>[
(q
-p)i
+
k
]
mod
n
=0

=>
(q-p)i
+
k
=
Nn
[N
為自然數]

=>
i
=
(Nn
-k)
/(p-q)

i取自然數，則當
p，q滿足上面等式
即
存在一個自然數N，可以滿足Nn
-k
是
p
-
q
的倍數時，保證兩者相交。

特例：如果q
是p
的步長的兩倍，都從同一個起點開始，即
q
=
2p
,
k
=0,
那麼等式變為：
Nn=i：
即可以理解為，當第i次迭代時，i是圈的整數倍時，兩者都可以交，交點就是為起點。
2.如何判斷單鏈表的環的長度？

這個比較簡單，知道q
已經進入到環里，保存該位置。然後由該位置遍歷，當再次碰到該q
位置即可，所迭代的次數就是環的長度。
3.
如何找到鏈表中第一個在環里的節點？

假設鏈表長度是L，前半部分長度為k-1，那麼第一個再環里的節點是k，環的長度是
n，
那麼當q=2p時，
什麼時候第一次相交呢？當q指針走到第k個節點時，q指針已經在環的第
k
mod
n
的位置。即p和q
相差k個元素，從不同的起點開始，則相交的位置為
n-k
從圖上可以明顯看到，當p從交點的位置（n-k)
,向前遍歷k個節點就到到達環的第一個幾點，節點k.
演算法就很簡單：
一個指針從p和q
中的第一次相交的位置起（n-k)，另外一個指針從鏈表頭開始遍歷，其交點就是鏈表中第一個在環里的交點。
4.
如果判斷兩個單鏈表有交？第一個交點在哪裡？

這個問題畫出圖，就可以很容易轉化為前面的題目。

將其中一個鏈表中的尾節點與頭節點聯系起來，則很容發現問題轉化為問題3，求有環的鏈表的第一個在環里的節點。

㈡ 在C語言中，到底是指針難 學還是演算法難學

從本質上來說，這應該屬於一個偽命題。這兩樣東西是不應該被放在一起比較的。
指針是被設計來解決具體的問題的，就好象是一件工具，要想生產一輛汽車，你沒有水壓機，用錘子也能敲一輛出來。只不過慢一點而已。
但如果沒有設計圖紙，不了解發動機的工作原理，想要憑小學水平獨立作一輛汽車，基本上不可能。
水壓機就類似於指針，工作原理就類似於演算法。
實際上也是如此，許多語言（例如JAVA）都沒有指針的概念，但也工作的很好。

回到哪個更難的問題。實際上，任何人經過一段時間的訓練後，都要以比較嫻熟的掌握指針的常用用法，並徹底了解指針的概念。但演算法不同，沒人敢說自己對所有演算法都掌握並能熟練運用了。
同樣，在C語言中，對指針本身的研究基本停止了，畢竟這只是一個工具，就象沒人肯研究錘子本身一樣。人們主要研究的還是演算法方法的東西。也就是怎麼把工具用的更好。
所以，演算法難學