关于数据结构和算法:PIPIOJ1496查找链表的中位数

题目形容

给定带头结点的单链表 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);
}