#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h> // INT_MAX等
#include <stdio.h>  // NULL等
#include <stdlib.h> // atoi( ), exit( )
#include <math.h> // floor( ), ceil( ), abs( ), OVERFLOW宏定义，其值为3。

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3

typedef int Status;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

//单链表的初始化
Status InitList(LinkList &L)
{ // 构造一个空的单链表L
   L=(LinkList)malloc(sizeof(LNode)); 
   if (!L) 
        exit(OVERFLOW);
   L->next=NULL; 
   return OK;
}

//输出链表 
Status visit(LinkList L)
{ //按序输出单链表的各个元素值
   LinkList p=L->next;
   while(p)
   {
     printf("%d ", p->data);
     p=p->next;
   }
   printf("\n");
   return OK;
}

//插入节点
Status ListInsert(LinkList &L,int i,ElemType e) 
{ // 在带头结点的单链线性表L中第i个位置之前插入元素e
    LinkList p = L; 
    int j = 0; 
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return ERROR;  
    LinkList newNode = (LinkList)malloc(sizeof(LNode)); 
    if (newNode == NULL) exit(-1);
    newNode->data = e;
    newNode->next = p->next; 
    p->next = newNode;
    return OK;
}

//归并链表
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) 
{ // 已知线性表La和Lb中的数据元素按值非递减排列。
// 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列
	
    LinkList pa = La->next; 
    LinkList pb = Lb->next; 
    Lc = La; 
    LinkList pc = Lc;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            LinkList temp = pb->next;
            pb->next = pa;
            pc->next = pb;
            pc = pb;
            pb = temp;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}

//逆转单链表，直接逆转
void ReverseList(LinkList L)
{
    if (L->next == NULL) return; 
    LinkList pre = NULL;
    LinkList cur = L->next;
    LinkList next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    L->next = pre;
}

//删除单链表中最小值元素
Status DeleteSmallest(LinkList L, ElemType &e)
{//删除单链表中最小值元素，并由e返回值，若不存在最小值元素，返回ERROR，否则返回OK。
    if (L->next == NULL) return ERROR; 
    LinkList prev = L, curr = L->next;
    LinkList min = curr; 
    LinkList minPrev = L; 

    curr = curr->next; 
    while (curr != NULL) {
        if (curr->data < min->data) {
            min = curr;
            minPrev = prev; 
        }
        prev = curr;
        curr = curr->next;
    }

    e = min->data; 
    minPrev->next = min->next; 
    free(min); 

    return OK;
}

//删除所有值为x的数据元素
void Delete_ALL_X(LinkList L, ElemType x) {
     LinkList p = L->next, prev = L;
    while (p != NULL) {
        if (p->data == x) {
            LinkList temp = p;
            prev->next = p->next; 
            p = p->next; 
            free(temp); 
        } else {
            prev = p; 
            p = p->next;
        }
    }
}

//查找单链表中最中间位置的值
Status FindMiddle(LinkList L, ElemType &e)
{//快速寻找单链表中最中间位置的结点，并由e返回值。若不存在中间位置，返回ERROR，否则返回OK。
    if (L == NULL || L->next == NULL) return ERROR;

    LinkList slow = L->next; 
    LinkList fast = L->next;
    int count = 0;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;    
        fast = fast->next->next; 
        count++;
    }
    if (fast == NULL) { 
        LinkList temp = L->next; 
        for (int i = 0; i < count - 1; i++) { 
            temp = temp->next;
        }
        e = temp->data; 
    } else {
        e = slow->data;
    }

    return OK;
}

//查找单链表中倒数第k个位置上的值（k为正整数）
Status FindLastK(LinkList L, int k, ElemType &e)
{//查找单链表中倒数第k个位置上的结点（k为正整数）。若查找成功，由e返回值，并返回OK；否则，只返回ERROR。
    if (L == NULL || L->next == NULL || k <= 0) return ERROR; 
    LinkList p1 = L->next;
    LinkList p2 = L->next;

    for (int count = 0; count < k; count++) {
        if (p2 == NULL) return ERROR; 
        p2 = p2->next;
    }

    while (p2) { 
        p1 = p1->next;
        p2 = p2->next;
    }
    
    e = p1->data; 
    return OK;
}

int main()
{
	LinkList Lc; 
	int j, n;
	ElemType e;
	InitList(Lc); // 创建空表Lc
	scanf("%d",&n);
	for(j=1;j<=n;j++)
	{
		scanf("%d",&e);
		ListInsert(Lc,j,e);
	}
	printf("Lc= "); // 输出表Lc的内容
	visit(Lc);

	FindMiddle(Lc,e);
	printf("链表Lc中间元素=%d\n",e); //奇数个，偶数个

	int k;
	scanf("%d",&k);
	Status result = FindLastK(Lc,k,e);
	if(result)
		printf("链表Lc中倒数第%d个元素=%d\n",k,e); 
	else
		printf("链表Lc中找不到倒数第%d个元素\n",k);
	return 0;
}