1.確認了解題意，如果對題意了解不清，應(yīng)該向面試人員問清楚
2.明確題意后，首先思考找到一個復(fù)雜度可以接受的正確算法，并表述出來，注意可以在草稿紙上寫寫劃劃，進行驗證
3.觀察復(fù)雜度能否再次降低
4.書寫程序時，一定要認真，堅決防止出現(xiàn)邏輯錯誤，并根據(jù)程序具體分析可能的極端情況，處理好邊界，并自己進行用例測試，以驗證程序。
節(jié)點的定義如下：
typedef struct list {
int key;
struct list *next;
}list;
(1)已知鏈表的頭結(jié)點head,寫一個函數(shù)把這個鏈表逆序 ( Intel)
list * reverse(list * head){
list * h = head;
list * new_head = NULL,*temp;
if(h==NULL) return h;//如果是空鏈表
do{
temp = h;
h = h -> next;
temp -> next = new_head;
new_head = temp;
}while(h != NULL && h != head)//檢測是循環(huán)鏈表
return new_head;
}
其實還要注意一點，鏈表內(nèi)部是否包含小環(huán)。
(2)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序。(保留所有結(jié)點，即便大小
相同）
list * merge (list *list1_head, list *list2_head){
}
其實需要問一下，head1 head2是否都是從大到小，這點一定要明確，不能默認兩個是相同的規(guī)格排序。
(3)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序，這次要求用遞歸方法進行。 (Autodesk)
list * merge (list *list1_head, list *list2_head){
list * res;
if(list1_head == NULL) return list2_head;
if(list2_head == NULL) return list1_head;
if(list1_head->key > list2_head->key){
res = list1_head;
res->next = merge(list1_head->next,list2_head);
}else{
res = list2_head;
res->next = merge(list1_head,list2_head->next);
}
return res;
}
(4)寫一個程序，計算鏈表的長度
unsigned int list_len(list *head){
unsigned int len = 0;
list * h = head;
if(h == NULL)return 0;
d0{
len++;
h = h->next;
}while(h != NULL && h != head)
return len;
}
如果是循環(huán)鏈表？
(5)有一個鏈表L,其每個節(jié)點有2個指針，一個指針next指向鏈表的下個節(jié)點，另一個random隨機指向鏈表中的任一個節(jié)點，可能是自己或者為空，寫一個程序，要求復(fù)制這個鏈表的結(jié)構(gòu)并分析其復(fù)雜性。
這個題目的思路很巧妙。當然簡單的方法，可以利用一個map或者hash，將鏈表的random指針的指向，保存起來。這樣有O(n)存儲空間的浪費，時間基本可以接近O(n).
實際上可以這樣來做：我們將新的鏈表節(jié)點，插入到原來鏈表節(jié)點當中，并且修改原來的鏈表的random指針，使得該指針由我們現(xiàn)在的新節(jié)點所有。實際上形成下面這樣一種結(jié)構(gòu)，同時將原來o的random指針的值，復(fù)制給它后面的現(xiàn)在的@的random指針，該結(jié)構(gòu)如下：
o->@->o->@->o->@->NULL
現(xiàn)在可以利用@擁有的random指針方便的找到它真正的random指針。因為原來的@的random指針指向o的random指針，只要把讓@->random=@->random->next,random就是真正的那個指針了，然后我們再把@從這個鏈表中刪除。
(6)給你一個單向鏈表的頭指針，可能最后不是NULL終止，而是循環(huán)鏈表。題目問你怎么找出這個鏈表循環(huán)部分的第一個節(jié)點。
這個原來的判斷鏈表環(huán)的擴展，需要求出環(huán)的開始點。只要稍微對原來的方法進行擴展，也就可以解決這個問題。使用兩個指針一個步長為1，另一個步長為2，如果第二個指針可以追上第一個指針，則說明有環(huán)。這樣我們首先可以求出環(huán)的長度L，然后在設(shè)兩個步長為1的指針，讓他們間距為L，這樣第一個相等的地方，就是環(huán)的起點。
還有一個更好的方法，就是在步長為1，步長為2指針相遇后，再從頭開始一個步長為1的指針，然后開始步長為1的指針繼續(xù)行進，當這兩個指針相遇的地方就是環(huán)的起點。
(7)（華為面試題）找出單向鏈表中中間結(jié)點
這個可以借鑒上面的方法，利用步長為1，步長為2指針，當步長為2的指針到達末尾時，指針1就剛好達到中間。
(8)題目：給定鏈表的頭指針和一個結(jié)點指針，在O(1)時間刪除該結(jié)點。鏈表結(jié)點的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
實際上我們可以將該節(jié)點的下一個節(jié)點的值copy到這個節(jié)點，然后刪除下一個節(jié)點。這樣實際上就將一個不能處理的情況，通過一種技巧轉(zhuǎn)化成了我們可以處理的正常情況。
但是還需要注意下面這個邊界情況：如果要刪除的是尾指針？這就意味著當前節(jié)點沒有下一個節(jié)點。
通過這點我們也可以發(fā)現(xiàn)，如果認真考慮各個因素，思路清晰，還是很容易發(fā)現(xiàn)各種異常情況的，保證嚴謹?shù)乃伎肌?/font>
(9)如何檢查一個單向鏈表上是否有環(huán)?
見(6)
(10)查找鏈表中倒數(shù)第k個結(jié)點
這個可以參考(7),我們可以設(shè)置步長相同，間距為k的指針，其特點在當內(nèi)存無法存放所有元素，需要從硬盤讀取時，性能卓越，k在可以接受的情況下可以一次讀取到內(nèi)存，大大提高了效率。
但是仍需要注意考慮邊界情況：
（細節(jié)，如，假如鏈表的長度不足m，它就不存在m個元素，因此必須在兩個指針的出發(fā)階段檢查最先出發(fā)的當前指針是否已經(jīng)到了鏈表尾。）
(11)題目：兩個單向鏈表，開頭結(jié)點不一樣, 在中間某處開始, 結(jié)點一樣了,找出它們的第一個公共結(jié)點。
這個問題，可以通過判斷最后一個節(jié)點是否相同，判斷是否相交。如果相交，可以統(tǒng)計兩個鏈表的長度，設(shè)一個為a，一個為b，然后這樣再搞兩個指針，一個先走|a-b|步，另一個再走，當它們相等時就是第一個公共結(jié)點。
再附三個有意思的小題，雖然不是鏈表相關(guān)的。
1.如何判斷一個整數(shù)是不是完全平方數(shù) (不允許開方). 單調(diào)函數(shù)可以二分查找。
2.不知長度的日志文件, 如何等概率選出100條。
3.一個唱片, 可以被分成8個大小一樣的小扇形. 要求給每個扇形涂上紅色或者藍色, 使得唱片旋轉(zhuǎn)起來以后, 按照順序讀出顏色序列, 就能判斷唱片是順時針旋轉(zhuǎn)還是逆時針。
