面試題快慢鏈表和快慢指針。本站提示廣大學習愛好者：（面試題快慢鏈表和快慢指針）文章只能為提供參考，不一定能成為您想要的結果。以下是面試題快慢鏈表和快慢指針正文

面試題快慢鏈表和快慢指針

投稿：lqh

騰訊的一道面試題：如何快速找到位置長度單鏈表的中間節點？普通方法，就是先遍歷，在從頭找到2/length的中間節點。算法復雜度是：O(3*n/2)。而更快的方法就是利用快慢指針的原理。

快慢鏈表：利用標尺的思想，設置兩個指針（一快一慢）*serach和*mid，剛開始都指向單鏈表的頭結點。但是*search指針的移動速度是*mid的兩倍。當*search到尾結點的時候，mid剛好到了中間。算法復雜度是：O(n/2)

int GetMidNode(LinkList *L,int elem){
  LinkList *search,*mid;
  mid = search = L; //指向頭結點
  while (search->next != NULL){ //當存在下個結點的時候 
    if (search->next->next!=NULL) {//檢查下個的下個節點是否為空 
      search = search->next->next;
      mid = mid->next;
    } 
    else
      search = search->next;
  }
  elem = mid->data;
  return elem;
} 

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！