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

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

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

   代碼如下：
   

#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é)點(diǎn) 
   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é)點(diǎn)       
    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é)點(diǎn) 
   Node * q = root ;
   bool flag = false ;  //判讀是否存在倒數(shù)第k個(gè)數(shù)字 
   
   while(p->next) //使用頭結(jié)點(diǎn) 
   {
      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 閱讀(1396) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 算法相關(guān)