课堂练习： 查找链表的中间结点

这是一个流传很广的面试题：已知一个链表的头结点，结点数未知。请找出链表的中间结点，这里的中间结点的意思是。如果结点数为5个，则中间结点是第3个。如果结点数是6个。则第3,4个任意为中间结点。

 

算法分析：如果一开始就用两次扫描法来（一次计数，第二次找出中间结点），这个算法显得有点简单。一次般大部分解法是要求做两个指针，一个指针在链表移动两步，一个指针在链表移动一步。当移动二步的指针到尾后，移动一步就指针指向就是中间结点。

 

要求一用C语言自写数据结构来实现这一算法：

 

struct node {
  struct node * next;
  int data;
};


struct node * find_mid(struct node * p_first)
{
   struct node * p_node1= p_first;
   struct node * p_node2= p_first;
   
   if(p_node1 == NULL)
      return NULL;
   
   while(1)
   {
      if(p_node1->next == NULL)
         break;
                
         
      if(p_node2->next->next == NULL)
        break;
        
       p_node1 = p_node1->next ;
        
       p_node2 = p_node2->next->next;
                         
   }
   
   return p_node1;
}

在上C++，STL的课程时，我会要求学员用list容器来实现这个算法，（不准使用 .size())这个有一些难度。

因为STL的iterator只知道到没有到尾，而没办法判断是否越界。如果使用iterator+2,很有可能越界，而无未能判断结束（实测程序正是如此），另外list没有重载+和+=。不能用加2。

 

所以这个题变得有点象脑筋急转弯了，怎么利用现有方法实现算法？我提供一个思路，就是把加2步算法，拆成两步，每一步都要判断it !=list.end()即可。

 

下面是一个同学提供比较好的算法.

 

 

 

#include <iostream>
using namespace std;

#include <list>


typedef list<int> int_list;


int find_mid(int_list & list)
{
  int_list::iterator it1,it2;
  
  for(it1=it2=list.begin(); it2!=list.end() && ++it2 != list.end() ; it2++,it1++);
  
  return *it1;
  
}


int main()
{
  int_list list ;
  
  for(int i=0 ; i < 100 ; i++)
     list.push_back(i);
     
 cout << find_mid(list) <<endl;
}