题目形容

给定带头结点的单链表L，假如L存储了n个元素(n为奇数，是未知的)。设计算法返回该链表两头的那个元素。要求仅对链表进行一次遍历。

输出

输出N个数字，不必关怀N是多少，应用while循环读入链表中元素，直至EOF。(0<N≤1e5)

输入

输入链表最两头的元素。

样例输出

1 2 3 4 5

样例输入

3

解题思路

用一个全局变量count统计链表元素的个数，中位数的位序=(count+1)/2。

C++参考解答

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct LNode {    ElemType data;    struct LNode* next;}LNode,*LinkList;int count = 0;//尾插法LinkList CreateList(LinkList& L) {    L = (LinkList)malloc(sizeof(LNode));    L->next = NULL;    LinkList s, r = L;    int x;    while (scanf("%d",&x)!=EOF){        s = (LinkList)malloc(sizeof(LNode));        s->data = x;        s->next = r->next;        r->next = s;        r = s;        count++;    }    r->next = NULL;    return L;}//输入链表中位数void ListMedian(LinkList L,int n) {    LinkList p = L->next;    int pos = (n + 1) / 2;    int i = 1;    while (i < pos) {        p = p->next;        i++;    }    printf("%d", p->data);}int main() {    LinkList L;    CreateList(L);    //PrintList(L);    ListMedian(L, count);}