.（等分链表）

2.（等分链表）假设单链表的节点类型为

struct Node{ double value_; Node* next_; };

单链表的最后一个节点的next_域为0。完成下面函数，它返回单链表的中间节点。

Node* middle(Node* first);

期中形参first指向单链表的第一个节点。如果单链表的结点个数为偶数，则返回任意一个中间节点均可。

/****************************************************************************/

/*==================================================================*/

/*****************************************************************************/

#include<iostream>

using namespace std;

 

#define SIZE 9                              //链表的长度；  

 

struct Node{

       double value_;

       Node* next_;

};

 

 

Node* middle(Node* first)                    //题目要求设计的函数；

{

       int n=0,mid;

       Node* currentPtr;

       currentPtr=first;

       while(currentPtr!=NULL){                 //统计链表长度；

              n++;

              currentPtr=currentPtr->next_;

       }

       if(n%2==1) { n++; }                     

       mid=n/2;

       currentPtr=first;

       for(int i=1;i<mid;i++){                  //将指针位置移到中间节点；

              currentPtr=currentPtr->next_;

       }

       return currentPtr;

}

 

 

int main()

{

       Node head,a[SIZE],*currentPtr;             //开始创建链表；

    a[0].value_=0;

       a[0].next_=NULL;

       for(int i=1;i<SIZE;i++){                   //链表元素取值从0开始，依次加1；

              a[i].value_=i;

              a[i-1].next_=&(a[i]);

       }

       a[i-1].next_=NULL;

       head=a[0];                                 //完成创建链表；

 

       cout<<"默认链表为："<<endl;                //开始输出；

       currentPtr=&head;                         

       while(currentPtr->next_!=NULL){

              cout<<currentPtr->value_<<"->";

              currentPtr=currentPtr->next_;

       }

       cout<<currentPtr->value_<<endl;            //输出完毕；

 

       currentPtr=middle(&head);                  //题中函数的运用；

       cout<<endl<<"单链表中间节点的值为："<<currentPtr->value_<<endl;

       return 0;

}

/****************************************************************************/

/*==================================================================*/

/****************************************************************************/