面试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 阅读(1383) 评论(0)  编辑 收藏 引用 所属分类: 算法相关