免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

1.確認(rèn)了解題意，如果對題意了解不清，應(yīng)該向面試人員問清楚
2.明確題意后，首先思考找到一個復(fù)雜度可以接受的正確算法，并表述出來，注意可以在草稿紙上寫寫劃劃，進(jìn)行驗(yàn)證
3.觀察復(fù)雜度能否再次降低
4.書寫程序時，一定要認(rèn)真，堅(jiān)決防止出現(xiàn)邏輯錯誤，并根據(jù)程序具體分析可能的極端情況，處理好邊界，并自己進(jìn)行用例測試，以驗(yàn)證程序。

節(jié)點(diǎn)的定義如下：
typedef struct list {
int key;
struct list *next;
}list;

(1)已知鏈表的頭結(jié)點(diǎn)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;
}

其實(shí)還要注意一點(diǎn)，鏈表內(nèi)部是否包含小環(huán)。

(2)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序。(保留所有結(jié)點(diǎn)，即便大小

相同）

list * merge (list *list1_head, list *list2_head){

}

其實(shí)需要問一下，head1 head2是否都是從大到小，這點(diǎn)一定要明確，不能默認(rèn)兩個是相同的規(guī)格排序。

(3)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序，這次要求用遞歸方法進(jìn)行。 (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)寫一個程序，計(jì)算鏈表的長度

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é)點(diǎn)有2個指針，一個指針next指向鏈表的下個節(jié)點(diǎn)，另一個random隨機(jī)指向鏈表中的任一個節(jié)點(diǎn)，可能是自己或者為空，寫一個程序，要求復(fù)制這個鏈表的結(jié)構(gòu)并分析其復(fù)雜性。

這個題目的思路很巧妙。當(dāng)然簡單的方法，可以利用一個map或者h(yuǎn)ash，將鏈表的random指針的指向，保存起來。這樣有O(n)存儲空間的浪費(fèi)，時間基本可以接近O(n).

實(shí)際上可以這樣來做：我們將新的鏈表節(jié)點(diǎn)，插入到原來鏈表節(jié)點(diǎn)當(dāng)中，并且修改原來的鏈表的random指針，使得該指針由我們現(xiàn)在的新節(jié)點(diǎn)所有。實(shí)際上形成下面這樣一種結(jié)構(gòu)，同時將原來o的random指針的值，復(fù)制給它后面的現(xiàn)在的@的random指針，該結(jié)構(gòu)如下：

o->@->o->@->o->@->NULL

現(xiàn)在可以利用@擁有的random指針方便的找到它真正的random指針。因?yàn)樵瓉淼腀的random指針指向o的random指針，只要把讓@->random=@->random->next,random就是真正的那個指針了，然后我們再把@從這個鏈表中刪除。

(6)給你一個單向鏈表的頭指針，可能最后不是NULL終止，而是循環(huán)鏈表。題目問你怎么找出這個鏈表循環(huán)部分的第一個節(jié)點(diǎn)。

這個原來的判斷鏈表環(huán)的擴(kuò)展，需要求出環(huán)的開始點(diǎn)。只要稍微對原來的方法進(jìn)行擴(kuò)展，也就可以解決這個問題。使用兩個指針一個步長為1，另一個步長為2，如果第二個指針可以追上第一個指針，則說明有環(huán)。這樣我們首先可以求出環(huán)的長度L，然后在設(shè)兩個步長為1的指針，讓他們間距為L，這樣第一個相等的地方，就是環(huán)的起點(diǎn)。

還有一個更好的方法，就是在步長為1，步長為2指針相遇后，再從頭開始一個步長為1的指針，然后開始步長為1的指針繼續(xù)行進(jìn)，當(dāng)這兩個指針相遇的地方就是環(huán)的起點(diǎn)。

(7)（華為面試題）找出單向鏈表中中間結(jié)點(diǎn)
這個可以借鑒上面的方法，利用步長為1，步長為2指針，當(dāng)步長為2的指針到達(dá)末尾時，指針1就剛好達(dá)到中間。

(8)題目：給定鏈表的頭指針和一個結(jié)點(diǎn)指針，在O(1)時間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：
struct ListNode
{
      int        m_nKey;
      ListNode*  m_pNext;
};
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

實(shí)際上我們可以將該節(jié)點(diǎn)的下一個節(jié)點(diǎn)的值copy到這個節(jié)點(diǎn)，然后刪除下一個節(jié)點(diǎn)。這樣實(shí)際上就將一個不能處理的情況，通過一種技巧轉(zhuǎn)化成了我們可以處理的正常情況。

但是還需要注意下面這個邊界情況：如果要刪除的是尾指針？這就意味著當(dāng)前節(jié)點(diǎn)沒有下一個節(jié)點(diǎn)。
通過這點(diǎn)我們也可以發(fā)現(xiàn)，如果認(rèn)真考慮各個因素，思路清晰，還是很容易發(fā)現(xiàn)各種異常情況的，保證嚴(yán)謹(jǐn)?shù)乃伎肌?/font>