指针和算法

㈠ 判断单链表有没有环的算法中，至少需要几个指针

算法的思想是设定两个指针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语言中，对指针本身的研究基本停止了，毕竟这只是一个工具，就象没人肯研究锤子本身一样。人们主要研究的还是算法方法的东西。也就是怎么把工具用的更好。
所以，算法难学