面試100 -09 單鏈表中查找倒數(shù)第K個元素

      單鏈表中查找倒數(shù)第K個元素

      利用窗口機制解決問題，提高效率 ，查找一個單鏈表中，倒數(shù)第K個節(jié)點。
 方法(1) 首先查找到整個鏈表中的元素個數(shù)， 然后再一次遍歷該數(shù)組，找到第n-k+1個元素，即為所求。
        缺點：這需要兩次遍歷鏈表，當(dāng)鏈表中的元素個數(shù)很多的時候，耗費時間。
  方法(2)：
       定義兩個指針p,q，初始時都指向頭節(jié)點間，然后q向后移動，p則保持不動。
       當(dāng)P移動到第K個位置的時候，pq兩個節(jié)點同時向后移動，當(dāng)q達到鏈表尾部的時候， p節(jié)點所指向的位置，即為所求。
       這里充分利用了一個窗口機制，使用兩個間隔為K的指針，來達到目的。     
  延伸：
       求出一個排序完畢的數(shù)組中，相同數(shù)目元素出現(xiàn)次數(shù)大于100的元素。
       這也需要一個窗口機制。即比較a[i] 與a[i+100]兩個元素即可 。 

   代碼如下：
   

#include <iostream>
 using namespace std ;
 
 struct Node 
 {
    int data ;
    Node * next ;        
 } ;
 const int K = 4 ;
 
 void buildlist(Node * root , int x) ;
 void findK(Node * root);
 
 
 int main()
 {
   Node * root = 0 ; //頭結(jié)點 
   root = (Node *) malloc(sizeof(Node)) ;       
   root->data = 0;
   root->next = 0 ; 
       
   int x ;
   while(1)
   {
     cin>>x ;
     if(x == 0)
      break ;
            
    buildlist(root , x);
   }
   findK(root) ;
   system("pause") ;
   return 0 ;    
 }
 
 
 
 
 
 void buildlist(Node * root , int x) 
 {
 
   
    Node *  p = (Node *) malloc(sizeof(Node)) ; //創(chuàng)建新的表節(jié)點       
    p->data = x ;
    p->next = root->next ;          
    root->next = p ; 
               
  } 
 void findK(Node * root)
 {
   if(root == 0)
     return ;
   int i = 0 ;
   Node * p = root ;    //初始化均指向頭結(jié)點 
   Node * q = root ;
   bool flag = false ;  //判讀是否存在倒數(shù)第k個數(shù)字 
   
   while(p->next) //使用頭結(jié)點 
   {
      i++ ;
      if(i>=K)  //直到找到第 
      {
        q = q->next ;
        flag = true ;
      }
      p = p ->next ;    
   }
   if(flag)
    cout<<q->data<<endl  ;  
   else
    cout<<"error"<<endl  ;
   
        
 } 
  
  

posted on 2011-05-16 16:23 kahn 閱讀(1397) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關(guān)