- 论坛徽章:
- 8
|
今日面试题：
快排(QuickSort)单向链表(Singly Linked List)。
============================
乾坤大挪移的分析
题目：
给定一个单向链表，设计一个算法实现链表向右旋转K个位置。K是非负的整数。这题看起来简单，可真编程实现有陷阱啰。
举例：
给定：1->2->3->4->5->6->null 并且K=3，
则有：4->5->6->1->2->3->null。
分析：
这个题目，看起来是一个相对简单的题目。很多同学在面试的时候，如果看到这个题目，想必会心花怒放。可是，不要高兴得太早，你能够一次通过么？bug free？
如果这个题目，不能够一次性bug free的完成，考官会很失望，结果可能就是可想而知了。因为，在很多大公司的面试中，例如google，amazon等，往往更加看重的是bug free的能力，所以题目不会很难，但要求bug free的，这正好考察基本功和平时是否有严格训练。那要做到bug free就是至关重要的。
回到这个题目，我们简单说下这个题目的思路。
首先看看一些细节，比如，
1. 当K=0时，怎么办？
2. 当K等于链表长度时，怎么办？
3. 当K大于链表长度时，怎么办？
除了K=0，显然，我们需要知道尾指针。那么，第一步，扫描链表得到尾指针tail和链表的长度M。如果M=0，完毕。
接下来，计算需要移动的步数得到新的头指针之前的节点，就是，(K-1) % M，假设指向这个节点的指针为p。
那么将tail的next指向head，然后将head指向p的next，然后将p的next指向null。
这个解法可能需要扫描链表两次。如果我们事先知道链表的长度M的话，也许我们可以用双指针法：
有两个指针，第一个指针先走 M-(K % M)-1 步，然后第一个和第二个指针一起走，直到第一个指针指到终点，这个时候：
1. 第二个指针所指的next节点设置为新的头节点
2. 将第二个指针所指节点的next指针指向null
3. 将第一个指针所指的节点的next指针指向旧的头节点
下面，我们来看一个变化的类似题，以达到举一反三。
题目是这样的，对于有n个元素的数组 int a[n]={....}；写一个高效算法将数组内容循环左移m位。比如： int a[6] ={1,2,3,4,5,6} ，循环左移3位得到结果{456123}。
算法的基本思想如下：
还是用面试中的常用技巧，从一个例子出发。假设有一个包含8个数的数组 int a[8] = {1, 2, 3, 4, 5, 6, 7, 8}; 将其内容循环左移3位，即左移后的结果是{4, 5, 6, 7, 8, 1, 2, 3}。
从例子可以看出，将1,2,3移到了数组的最后，从4开始，直到8都往前移动了3个位置。因此我们可设想将1,2,3看成一个整体先和4, 5, 6交换, 再和7, 8交换。
第一次交换的结果：
4, 5, 6, 1, 2, 3, 7, 8
由于7，8只有两位，因此第二次交换只和1，2，3中的1,2进行交换。结果如下：
4, 5, 6, 7, 8, 3, 1, 2。
可以看出，前五位已经满足了最终结果，只有后3位还不满足最终结果。但是只要将3, 1, 2看成一个子数组，再将这个子数组循环左移1位，即可变成1, 2, 3。
因此在移动元素时可将要左移的m位看成一个整体（如上例中的1, 2, 3)，依次和它后面的相同位数的数组元素交换，如果后面的元素不足m位，假设为t位，t < m，那么只交换t位，这样，前面的数组元素（前 n - m 个元素一定满足条件）。
最后将后面m个元素看成一个子数组，再对其进行循环左移m - n % m位。
算法的时间复杂度为O(n)，应该少于最基本循环算法的O(mn)，空间复杂度为O(1)。
|
|
免费注册
发表于 2013-08-07 09:18
