今日面試題：

快排(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)。