今日面試題：

快排(QuickSort)單向鏈表(Singly Linked List)。

乾坤大挪移的分析

題目：

給定一個(gè)單向鏈表，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)鏈表向右旋轉(zhuǎn)K個(gè)位置。K是非負(fù)的整數(shù)。這題看起來簡單，可真編程實(shí)現(xiàn)有陷阱啰。

舉例：

給定：1->2->3->4->5->6->null 并且K=3，

則有：4->5->6->1->2->3->null。

分析：

這個(gè)題目，看起來是一個(gè)相對(duì)簡單的題目。很多同學(xué)在面試的時(shí)候，如果看到這個(gè)題目，想必會(huì)心花怒放。可是，不要高興得太早，你能夠一次通過么？bug free？

如果這個(gè)題目，不能夠一次性bug free的完成，考官會(huì)很失望，結(jié)果可能就是可想而知了。因?yàn)椋诤芏啻蠊镜拿嬖囍校鏶oogle，amazon等，往往更加看重的是bug free的能力，所以題目不會(huì)很難，但要求bug free的，這正好考察基本功和平時(shí)是否有嚴(yán)格訓(xùn)練。那要做到bug free就是至關(guān)重要的。

回到這個(gè)題目，我們簡單說下這個(gè)題目的思路。

首先看看一些細(xì)節(jié)，比如，

1.     當(dāng)K=0時(shí)，怎么辦？
2.     當(dāng)K等于鏈表長度時(shí)，怎么辦？
3.     當(dāng)K大于鏈表長度時(shí)，怎么辦？

除了K=0，顯然，我們需要知道尾指針。那么，第一步，掃描鏈表得到尾指針tail和鏈表的長度M。如果M=0，完畢。

接下來，計(jì)算需要移動(dòng)的步數(shù)得到新的頭指針之前的節(jié)點(diǎn)，就是，(K-1) % M，假設(shè)指向這個(gè)節(jié)點(diǎn)的指針為p。

那么將tail的next指向head，然后將head指向p的next，然后將p的next指向null。

這個(gè)解法可能需要掃描鏈表兩次。如果我們事先知道鏈表的長度M的話，也許我們可以用雙指針法：

有兩個(gè)指針，第一個(gè)指針先走 M-(K % M)-1 步，然后第一個(gè)和第二個(gè)指針一起走，直到第一個(gè)指針指到終點(diǎn)，這個(gè)時(shí)候：

1.     第二個(gè)指針?biāo)傅膎ext節(jié)點(diǎn)設(shè)置為新的頭節(jié)點(diǎn)
2.     將第二個(gè)指針?biāo)腹?jié)點(diǎn)的next指針指向null
3.     將第一個(gè)指針?biāo)傅墓?jié)點(diǎn)的next指針指向舊的頭節(jié)點(diǎn)

下面，我們來看一個(gè)變化的類似題，以達(dá)到舉一反三。

題目是這樣的，對(duì)于有n個(gè)元素的數(shù)組 int a[n]={....}；寫一個(gè)高效算法將數(shù)組內(nèi)容循環(huán)左移m位。比如： int a[6] ={1,2,3,4,5,6} ，循環(huán)左移3位得到結(jié)果{456123}。

算法的基本思想如下：

還是用面試中的常用技巧，從一個(gè)例子出發(fā)。假設(shè)有一個(gè)包含8個(gè)數(shù)的數(shù)組 int a[8] = {1, 2, 3, 4, 5, 6, 7, 8}; 將其內(nèi)容循環(huán)左移3位，即左移后的結(jié)果是{4, 5, 6, 7, 8, 1, 2, 3}。

從例子可以看出，將1,2,3移到了數(shù)組的最后，從4開始，直到8都往前移動(dòng)了3個(gè)位置。因此我們可設(shè)想將1,2,3看成一個(gè)整體先和4, 5, 6交換, 再和7, 8交換。

第一次交換的結(jié)果：  4, 5, 6, 1, 2, 3, 7, 8

由于7，8只有兩位，因此第二次交換只和1，2，3中的1,2進(jìn)行交換。結(jié)果如下：  4, 5, 6, 7, 8, 3, 1, 2。

可以看出，前五位已經(jīng)滿足了最終結(jié)果，只有后3位還不滿足最終結(jié)果。但是只要將3, 1, 2看成一個(gè)子數(shù)組，再將這個(gè)子數(shù)組循環(huán)左移1位，即可變成1, 2, 3。

因此在移動(dòng)元素時(shí)可將要左移的m位看成一個(gè)整體（如上例中的1, 2, 3)，依次和它后面的相同位數(shù)的數(shù)組元素交換，如果后面的元素不足m位，假設(shè)為t位，t < m，那么只交換t位，這樣，前面的數(shù)組元素（前 n - m 個(gè)元素一定滿足條件）。

最后將后面m個(gè)元素看成一個(gè)子數(shù)組，再對(duì)其進(jìn)行循環(huán)左移m - n % m位。

算法的時(shí)間復(fù)雜度為O(n)，應(yīng)該少于最基本循環(huán)算法的O(mn)，空間復(fù)雜度為O(1)。