|
题目： 给若干个数字，默认为int类型，要求使用单链表存放，现需要寻找该单链表中位于最中间的数字，要求使用一种在时间和空间上都高效的算法实现。
思想： 单链表是一种线性结构，每个元素只可有他的前驱结点进行访问，若使用一般方法对单链表进行逐个遍历看是否为那个位于最中间的数字显然是不符合要求的，所以我们采取其他的方法，类似于标尺一般————使用双指针，都指向头指针，一个快一个慢，快指针的后移速度是慢指针后移速度的两倍，慢指针其实就是要寻找的位于最中间的数字，当过程中快指针为NULL时候停止（有偶数个数字的时候默认没有位于最中间的数字）。
代码实现：
#include
#include
#include
typedef struct LinkNode
{
int data;
struct LinkNode *next;
}LinkNode,*LinkList;
void InitLInkList(LinkList &L)
{
L = (LinkList)malloc(sizeof(LinkNode));
L->next = NULL;
}
void Insert(LinkList &L,int x)
{
LinkList p;
p = (LinkList)malloc(sizeof(LinkNode));
p->data = x;
p->next = L->next;
L->next = p;
}
void Print(LinkList L)
{
while(L->next!=NULL)
{
printf("%d ",L->next->data);
L = L->next;
}
}
void Search(LinkList L)
{
int flag = 1;
LinkList p = L;
LinkList mid = L;
while(p!=NULL)
{
if(p->next == NULL)
{
flag = 0;
break;
}
p = p->next->next;
mid = mid->next;
}
if(flag==1)
{
printf("位于最中间元素是：%d\n",mid->data);
}
else
{
printf("位于最中间的元素不存在！\n");
}
}
int main() {
int n;
int e;
LinkList L;
InitLInkList(L);
printf("请输入要存放的数据个数：\n");
scanf("%d",&n);
printf("请输入要存放的数据：\n");
for(int i=0; i |