目录

 

一、思路

二、代码

三、测试

四、总结

---

一、思路

先上关键代码

LinkList front_Node = L->next; LinkList later_Node = L->next; while(front_Node->next != NULL) { if(front_Node->next->next !=NULL) front_Node = front_Node->next->next; else break; //注意break的位置 later_Node = later_Node->next; } return later_Node;

用两个指针，分别是快指针和慢指针，让他们同时出发，不同的是快指针一次前进两个结点，慢指针则前进一个，这样当快指针到达尾结点时，慢指针也到达中间结点。不过其中有些细节我们需要注意。

①当结点个数是奇数时，没有什么问题，图示如下

 

②当结点个数是偶数时，要注意边界问题，我们及早判断到达终点，跳出循环，图示如下

LinkList front_Node = L->next; LinkList later_Node = L->next; while(front_Node->next != NULL) { if(front_Node->next->next !=NULL) front_Node = front_Node->next->next; else break; later_Node = later_Node->next; } return later_Node; }

这里我用到了一个if判断加上一个break语句，这个break的位置，其实就影响了中间结点是偏左，还是偏右那个结点，这给我们了一些灵活性，这里我们break在前，所以是偏左则，完全可以改成右侧，只需要移动慢指针到上面即可。以下是右侧代码

LinkList front_Node = L->next; LinkList later_Node = L->next; while(front_Node->next != NULL) { later_Node = later_Node->next; if(front_Node->next->next != NULL) front_Node = front_Node->next->next; else break; } return later_Node;

二、代码

#include<iostream> #include "malloc.h" using namespace std; typedef struct LNode { int data; struct LNode * next; }LNode, *LinkList ; int tail_create_heahLinked_List(LinkList & L,int n) { if( n < 0) return 1; LinkList head = (LinkList)malloc(sizeof(LNode));//头结点的存储地址 if(NULL == head) return 1; //分配空间失败 L = head; //头指针L存储头结点P的地址，即头指针指向头结点 L->data = 0; //用头结点统计元素个数，刚开始为0个 L->next = NULL; //此时链表为空 LinkList temp = L; //此时temp其实就等于头结点，地址相同 for(int i = 0;i<n;i++) { LinkList List_Node = (LinkList)malloc(sizeof(LNode)); scanf("%d",&List_Node->data); L->data++; //每插入一个元素，头结点统计链表元素个数加一 List_Node->next = NULL; temp->next = List_Node; //尾插法，即链表中的元素顺序与输入相同 temp = temp->next; if(i == n-1 ){ temp->next = NULL; } } return 0; } LinkList Found_middle_node(LinkList L) { if( NULL == L || NULL == L->next || L->data == 0) return NULL; LinkList front_Node = L->next; LinkList later_Node = L->next; while(front_Node->next != NULL) { if(front_Node->next->next !=NULL) front_Node = front_Node->next->next; else break; later_Node = later_Node->next; } return later_Node; } void headlinked_List_Traverse(LinkList L) { cout<<"该链表的元素个数为:"<<L->data<<endl; LinkList p = L->next; while(p) { cout<<p->data<<" "; p = p->next; } cout<<endl; } int main() { while(1) { int num; cin>>num; LinkList L =NULL; if(!tail_create_heahLinked_List(L,num)) { headlinked_List_Traverse(L);//打印链表 LinkList middle_Node =NULL; middle_Node = Found_middle_node(L); if(NULL != middle_Node) cout<<"中间"<<"结点值为:"<<middle_Node->data<<endl; else cout<<"没有此结点"<<endl; } } return 0; }

 

 

三、测试

这里我们规定当结点个数为偶数时，返回偏左侧结点值

1 1 该链表的元素个数为:1 1 中间结点值为:1 2 1 2 该链表的元素个数为:2 1 2 中间结点值为:1 3 1 2 3 该链表的元素个数为:3 1 2 3 中间结点值为:2 4 1 2 3 4 该链表的元素个数为:4 1 2 3 4 中间结点值为:2 5 1 2 3 4 5 该链表的元素个数为:5 1 2 3 4 5 中间结点值为:3 10 1 2 3 4 5 6 7 8 9 10 该链表的元素个数为:10 1 2 3 4 5 6 7 8 9 10 中间结点值为:5

这里我们规定当结点个数为偶数时，返回偏右侧结点值

1 1 该链表的元素个数为:1 1 中间结点值为:1 2 1 2 该链表的元素个数为:2 1 2 中间结点值为:2 3 1 2 3 该链表的元素个数为:3 1 2 3 中间结点值为:2 4 1 2 3 4 该链表的元素个数为:4 1 2 3 4 中间结点值为:3 5 1 2 3 4 5 该链表的元素个数为:5 1 2 3 4 5 中间结点值为:3 10 1 2 3 4 5 6 7 8 9 10 该链表的元素个数为:10 1 2 3 4 5 6 7 8 9 10 中间结点值为:6

四、总结

这里用到了一个数学的小技巧，即奇数 * 2 = 偶数，数学无处不在。