今日面试题:

快排(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-07-08发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。