快慢指针问题的讨论
又是一个非常常见的问题.
最近在缓慢的学习 leetcode 上面的习题. 看到了有些问题都和这个有点关系,就总结下来.
原始问题大家都很熟悉了.
141. Linked List Cycle I
给定链表,发现其中是否有环.
暴力手段,就是保存所有自链表头部节点开始的所有节点,然后一边向后遍历,一边向前比较,如果没有重复出现节点,那么不存在环路;如果有重复出现的节点,那么检测到存在环路.
这种方式,因为需要保持已经遍历过的节点,因此需要较多的存储空间. 同时因为比较过程也比较复杂,时间复杂度也不好.
这个问题可以通过快慢指针很好的解决.
- 慢指针:每次迭代,向前移动一个节点 `pSlow = pSlow->next;`
- 快指针:每次迭代向前移动两个节点 `pFast = pFast->next->next;`
如果pFast或者pFast->next为NULL,则检查到链表尾部,发现没有存在环路; 如果发现 pFast == pSlow 则存在环路.
需要注意的一点是,当发现 pFast == pSlow 的时候,并不一定是链表出现环路位置的入口位置.
暴力手段之所以复杂,主要在于没有充分利用题目的限定条件. 题目考虑是否出现环路的问题,如果出现环路,那么必然会遍历到已经遍历过的节点.但是此时,并不需要第一次检查到遍历过的节点是,就立刻检查出来. 而因为环路存在,后续被继续遍历的节点,实际上也会被再次检查到.我们在之后的位置,检查到环路也是可以的. 快慢指针的方案,就放弃了”在环路入口位置就检查到环路存在”这一点,从而另辟蹊径.
142. Linked List Cycle II
给定链表,如果存在环路,找到环路的入口位置;如果不存在环路,返回`NULL`
很明显,这个问题在141问题基础上更进一步. 例如141的快慢指针方案,可以简单快速的找到入口的存在.
假设存在环路, 环路部分节点个数为r, 从头部到环路部分节点个数为l. 那么到快慢指针相遇,慢指针走了s步,快指针走可2s步.因为快指针走的快,在环路上饶圈子,设饶了k圈,整圈之外又走了r0步.
则
s = l + r0
2s = l + kr + r0
=>
2(l + r0) = l + kr + r0
r0 = kr - l
因此考虑如何找到环路的入口处,也就是寻找到消除r0的方式.所以消除r0的方式,就是再移动 l 步.因此将一个指针放回到链表入口head处,然后另一个指针继续在环路上转圈子,直到二者再次相遇,这个时候,就是环路的入口位置.
148. Sort List
排序一个链表.
根据链表的特性,合并排序最为简单,因为链表的合并过程,可以之间通过链表的指针过程进行,因此不需要数据的额外搬运过程.
如果链表当中没有环路的话,使用快慢指针可以快速得到链表的中点位置. 当快指针走到链表的尾部的时候,慢指针刚好在链表的中点位置.
在合并排序一个链表的时候,就利用这个技巧可以定位到链表的中间位置,然后分别对前后各一半进行排序,然后再把二者合并起来.
234. Palindrome Linked List
检查链表是否是回文.
同样需要寻找链表的中间节点,需要选择链表的中间节点,那么就可以将链表的后半部分逆序,然后就变成链表的前半部分和(逆序后的)后半部分的比较问题.比较结束后,可以再次将后半部分逆序回去,从而保持链表不变.
一个小细节,就是链表的长度是奇数的时候,这个时候链表不能够均分为两部分,我们需要找的是链表的后中位点,因此需要pSlow向前再移动一次.
以上两个小问题,仅仅是根据快慢指针需要链表的中间位置,非常简单.
202. Happy Number
检查一个数是否是happy number.
对数字可以进行一种迭代,各位数字的平方和.反复进行迭代,如果可以迭代到1,那么因为1的平方和就是1,迭代就会停止,这个数字就是happy number,如果可以循环进行这种迭代,一直到无法迭代到1,那么就不是happy number.
比如:19就是happy number.因为
1 ^ 2 + 9 ^ 2 = 82
8 ^ 2 + 2 ^ 2 = 68
6 ^ 2 + 8 ^ 2 = 100
1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1
显然这个问题和快慢指针的问题,有一定的相似之处,都是检查环路或者尾部的存在性的.
首先可以定义好迭代函数iter. “快指针”迭代两次,”慢指针”迭代一次,如果快指针迭代过程中可以达到1,则是happy number,如果”快指针”,”慢指针”二者相等(相遇),则说明可以循环进行,不是happy number.
因此可以看到这个问题和快慢指针问题是同构的.只是,对于链表环路检查问题,迭代函数是->next,尾部节点是NULL;对于这个问题迭代函数是上述计算过程 iter 而已.尾部节点是1.
(\x -> x->next, nil) <=> (iter, 1)
287. find duplicate nums
已知数组中包含`n + 1`个元素,任意元素在`[1, 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]
下标为
0, 1, 2, 3, 4
这个数组表示的函数中A(1) = A(3) = 2, 则这个数组的迭代过程(设从0开始):
0 -> 1 -> {2 -> 4 -> 3} -> 2 -> 4 -> 3 -> ...
可以看到2->4->3出现了一个环路.而问题就是寻找这个环路的入口节点.这也是链表环路的同构问题可以,完全可以通过快慢指针的技巧完成.