題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應(yīng)出程序員思維是否嚴(yán)密，在微軟之后已經(jīng)有很多公司在面試時(shí)采用了這道題。
為了正確地反轉(zhuǎn)一個(gè)鏈表，需要調(diào)整指針的指向。與指針操作相關(guān)代碼總是容易出錯(cuò)的，因此在動(dòng)手寫程序之前作全面的分析。在面試的時(shí)候不急于動(dòng)手而是一開始做仔細(xì)的分析和設(shè)計(jì)，將會(huì)給面試官留下很好的印象，因?yàn)樵趯?shí)際的軟件開發(fā)中，設(shè)計(jì)的時(shí)間總是比寫代碼的時(shí)間長。與其很快地寫出一段漏洞百出的代碼，遠(yuǎn)不如用較多的時(shí)間寫出一段健壯的代碼。
為了將調(diào)整指針這個(gè)復(fù)雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設(shè)下圖中l(wèi)、m和n是三個(gè)相鄰的結(jié)點(diǎn)：
a戀…氀 mànà…
假設(shè)經(jīng)過若干操作，我們已經(jīng)把結(jié)點(diǎn)l之前的指針調(diào)整完畢，這些結(jié)點(diǎn)的m_pNext指針都指向前面一個(gè)結(jié)點(diǎn)�，F(xiàn)在我們遍歷到結(jié)點(diǎn)m。當(dāng)然，我們需要把調(diào)整結(jié)點(diǎn)的m_pNext指針讓它指向結(jié)點(diǎn)l。但注意一旦調(diào)整了指針的指向，鏈表就斷開了，如下圖所示：
a戀…l洀 nà…
因?yàn)橐呀?jīng)沒有指針指向結(jié)點(diǎn)n，我們沒有辦法再遍歷到結(jié)點(diǎn)n了。因此為了避免鏈表斷開，我們需要在調(diào)整m的m_pNext之前要把n保存下來。
接下來我們試著找到反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。不難分析出反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)是原始鏈表的尾位結(jié)點(diǎn)。什么結(jié)點(diǎn)是尾結(jié)點(diǎn)?就是m_pNext為空指針的結(jié)點(diǎn)。
基于上述分析，我們不難寫出如下代碼：
///////////////////////////////////////////////////////////////////////
// Reverse a list iteratively
// Input: pHead - the head of the original list
// Output: the head of the reversed head
///////////////////////////////////////////////////////////////////////
ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL)
{
// get the next node, and save it at pNext
ListNode* pNext = pNode->m_pNext;
// if the next node is null, the currect is the end of original
// list, and it's the head of the reversed list
if(pNext == NULL)
pReversedHead = pNode;
// reverse the linkage between nodes
pNode->m_pNext = pPrev;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
擴(kuò)展：本題也可以遞歸實(shí)現(xiàn)。
左旋轉(zhuǎn)字符串
題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時(shí)間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
分析：如果不考慮時(shí)間和空間復(fù)雜度的限制，最簡單的方法莫過于把這道題看成是把字符串分成前后兩部分，通過旋轉(zhuǎn)操作把這兩個(gè)部分交換位置。于是我們可以新開辟一塊長度為n+1的輔助空間，把原字符串后半部分拷貝到新空間的前半部分，在把原字符串的前半部分拷貝到新空間的后半部分。不難看出，這種思路的時(shí)間復(fù)雜度是O(n)，需要的輔助空間也是O(n)。
接下來的一種思路可能要稍微麻煩一點(diǎn)。我們假設(shè)把字符串左旋轉(zhuǎn)m位。于是我們先把第0個(gè)字符保存起來，把第m個(gè)字符放到第0個(gè)的位置，在把第2m個(gè)字符放到第m個(gè)的位置…依次類推，一直移動(dòng)到最后一個(gè)可以移動(dòng)字符，最后在把原來的第0個(gè)字符放到剛才移動(dòng)的位置上。接著把第1個(gè)字符保存起來，把第m+1個(gè)元素移動(dòng)到第1個(gè)位置…重復(fù)前面處理第0個(gè)字符的步驟，直到處理完前面的m個(gè)字符。
該思路還是比較容易理解，但當(dāng)字符串的長度n不是m的整數(shù)倍的時(shí)候，寫程序會(huì)有些麻煩，感興趣的朋友可以自己試一下。由于下面還要介紹更好的方法，這種思路的代碼我就不提供了。
我們還是把字符串看成有兩段組成的，記位XY。左旋轉(zhuǎn)相當(dāng)于要把字符串XY變成YX。我們先在字符串上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)字符串中字符的先后順序。把X翻轉(zhuǎn)后記為XT。顯然有(XT)T=X。
我們首先對X和Y兩段分別進(jìn)行翻轉(zhuǎn)操作，這樣就能得到XTYT。接著再對XTYT進(jìn)行翻轉(zhuǎn)操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我們期待的結(jié)果。
分析到這里我們再回到原來的題目。我們要做的僅僅是把字符串分成兩段，第一段為前面m個(gè)字符，其余的字符分到第二段。再定義一個(gè)翻轉(zhuǎn)字符串的函數(shù)，按照前面的步驟翻轉(zhuǎn)三次就行了。時(shí)間復(fù)雜度和空間復(fù)雜度都合乎要求。
參考代碼如下：
#include "string.h"
///////////////////////////////////////////////////////////////////////
// Move the first n chars in a string to its end
///////////////////////////////////////////////////////////////////////
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
int nLength = static_cast(strlen(pStr));
if(nLength > 0 || n == 0 || n > nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the strint
ReverseString(pSecondStart, pSecondEnd);
// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);
}
}
return pStr;
}
///////////////////////////////////////////////////////////////////////
// Reverse the string between pStart and pEnd
///////////////////////////////////////////////////////////////////////
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
