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

      單鏈表中查找倒數第K個元素

      利用窗口機制解決問題，提高效率 ，查找一個單鏈表中，倒數第K個節點。
 方法(1) 首先查找到整個鏈表中的元素個數， 然后再一次遍歷該數組，找到第n-k+1個元素，即為所求。
        缺點：這需要兩次遍歷鏈表，當鏈表中的元素個數很多的時候，耗費時間。
  方法(2)：
       定義兩個指針p,q，初始時都指向頭節點間，然后q向后移動，p則保持不動。
       當P移動到第K個位置的時候，pq兩個節點同時向后移動，當q達到鏈表尾部的時候， p節點所指向的位置，即為所求。
       這里充分利用了一個窗口機制，使用兩個間隔為K的指針，來達到目的。     
  延伸：
       求出一個排序完畢的數組中，相同數目元素出現次數大于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 ; //頭結點 
   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)) ; //創建新的表節點       
    p->data = x ;
    p->next = root->next ;          
    root->next = p ; 
               
  } 
 void findK(Node * root)
 {
   if(root == 0)
     return ;
   int i = 0 ;
   Node * p = root ;    //初始化均指向頭結點 
   Node * q = root ;
   bool flag = false ;  //判讀是否存在倒數第k個數字 
   
   while(p->next) //使用頭結點 
   {
      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 閱讀(1405) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關