筆者由于在找工作，所以近期最主要的任務(wù)就是準(zhǔn)備面試，不打無準(zhǔn)備之仗。只有你準(zhǔn)備充分了，那么你想要的機(jī)會(huì)才有機(jī)會(huì)入你懷中。
筆者會(huì)將準(zhǔn)備面試的學(xué)習(xí)過程記錄下來，方便自己復(fù)盤的同時(shí)也希望能給一道找工作的小伙伴們一些幫助。筆者準(zhǔn)備的內(nèi)容大綱如下
妥妥的去面試之?dāng)?shù)據(jù)結(jié)構(gòu)與算法（一）
下面是本篇博客的正菜部分：
倒數(shù)第K個(gè)節(jié)點(diǎn)
在一個(gè)單鏈表中找到倒數(shù)第k個(gè)節(jié)點(diǎn)
很容易想到先遍歷一次鏈表節(jié)點(diǎn)個(gè)數(shù)n，第二次遍歷只需要找第n-k+1個(gè)節(jié)點(diǎn)。
當(dāng)你說出這個(gè)想法的時(shí)候，面試官肯定會(huì)提示你他期待的答案是只允許遍歷一次鏈表
關(guān)鍵點(diǎn)：是否可以想到使用兩個(gè)指針，移動(dòng)過程中兩個(gè)所在位置始終相差k-1的距離。當(dāng)前一個(gè)指針移到尾部時(shí)，后一個(gè)指針正好指向倒數(shù)第k個(gè)結(jié)點(diǎn)。
public ListNode findKthTail(ListNode pHead, int k){
if(pHead == null || k<=0) return null;
ListNode pAHead = pHead;
ListNode pBehind = null;
//使前面的指針快與后面的節(jié)點(diǎn)k-1個(gè)節(jié)點(diǎn)位
for(int i=0;i<k-1;i++){
if(pAHead.next != null){ //容易忽視隱藏的邊界條件，有可能k的值大于節(jié)點(diǎn)數(shù)
pAHead = pAHead.next;
}else{
return null;
}
}
//讓兩個(gè)指針始終保持k-1個(gè)節(jié)點(diǎn)位，等前面的節(jié)點(diǎn)到尾節(jié)點(diǎn)時(shí)，后一個(gè)節(jié)點(diǎn)到達(dá)倒數(shù)第k個(gè)節(jié)點(diǎn)
pBehind = pHead;
while(pAHead.next != null){
pAHead = pAHead.next;
pBehind = pBehind.next;
}
return pBehind;
}
引申：如果讓一次遍歷找鏈表的中間結(jié)點(diǎn)可以使用類似的方法。只需要在指針移動(dòng)時(shí)，前一個(gè)指針一次移動(dòng)兩個(gè)節(jié)點(diǎn)，后一個(gè)指針一次移動(dòng)一個(gè)節(jié)點(diǎn)。前一個(gè)指針到達(dá)尾部時(shí)，后一個(gè)指針到達(dá)中間節(jié)點(diǎn)。
反轉(zhuǎn)鏈表
反轉(zhuǎn)一個(gè)單鏈表，返回它的頭節(jié)點(diǎn)。
很容易想到的是直接反轉(zhuǎn)，后一個(gè)節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)。但是會(huì)有一個(gè)問題，到為尾節(jié)點(diǎn)的時(shí)候，會(huì)發(fā)生鏈表中斷，這是因?yàn)槲补?jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為空。
關(guān)鍵點(diǎn)：要將前一個(gè)節(jié)點(diǎn)保存下來，所以要使用三個(gè)指針
public ListNode reverseListNode(ListNode pHead){
if(pHead ==null) return null;
ListNode pNewHead = null;
ListNode pPre = null;
ListNode pCur = pHead;
while(pCur !=null){
ListNode pNext = pCur.next;
if(pNext == null){ //找到新的頭節(jié)點(diǎn)
pNewHead = pCur;
}
pCur.next = pPre; //反轉(zhuǎn)
pPre = pCur;
pCur = pNext;
}
return pNewHead;
}
是否可以想到添加一個(gè)指針來保存之前的節(jié)點(diǎn)是解題的關(guān)鍵
