#include <stdio.h>
#include <stdlib.h>

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

// 带头结点
LinkList InitList() {
    LNode *h = (LNode *)malloc(sizeof(LNode));
    if (h == NULL) return NULL;
    h->next = NULL;
    return h;
}

// 带头结点
int ListInsert(LinkList l, int i, int e) {
    if (i < 1) return -1;
    LNode *p = l;
    int j = 0;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return -1;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return -1;
    s->next = p->next;
    p->next = s;
    s->data = e;
    return 1;
}

// 带头结点
int ListDelete(LinkList l, int i, int *e) {
    if (i < 1) return -1;
    LNode *p = l;
    int j = 0;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return -1;
    LNode *q = p->next;
    if (q == NULL) return -1;
    p->next = q->next;
    *e = q->data;
    free(q);
    return 1;
}

// 不带头结点
LinkList InitList1() {
    return NULL;
}

// 不带头结点
int ListInsert1(LinkList *l, int i, int e) {
    if (i < 1) return -1;
    if (i == 1) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) return -1;
        s->next = *l;
        s->data = e;
        *l = s;
        return 1;
    }
    LNode *p = *l;
    int j = 1;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return -1;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return -1;
    s->next = p->next;
    p->next = s;
    s->data = e;
    return 1;
}

// 不带头结点
int ListDelete1(LinkList *l, int i, int *e) {
    if (i < 1) return -1;
    if (i == 1) {
        LNode *q = *l;
        LNode *s = q->next;
        *e = q->data;
        free(q);
        *l = s;
        return 1;
    }
    LNode *p = *l;
    int j = 1;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return -1;
    LNode *q = p->next;
    if (q == NULL) return -1;
    p->next = q->next;
    *e = q->data;
    free(q);
    return 1;
}

// 通用接口
LNode * GetElem(LinkList l, int i) {
    if (i < 0) return NULL;
    LNode *p = l;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 通用接口
LNode * LocateElem(LinkList l, int e) {
    LNode *p = l;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

// 通用接口
int Length(LinkList l) {
    int len = 1;
    LNode *p = l;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

// 通用接口
void ListPrintf(LinkList l) {
    LNode *p = l;
    while (p != NULL) {
        printf("%i\n", p->data);
        p = p->next;
    }
}

// 通用接口
int Empty(LinkList l) {
    return l == NULL ? 1 : -1;
}

// 通用接口
void DestroyList(LinkList *l) {
    LNode *q = *l;
    LNode *next = NULL;
    while (q != NULL) {
        next = q->next;
        free(q);
        q = next;
    }
    *l = NULL;
}

// 通用接口: 前插操作
int InsertPriorLNode(LNode *n, int e) {
    if (n == NULL) return -1;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return -1;
    s->next = n->next;
    n->next = s;
    s->data = n->data;
    n->data = e;
    return 1;
}

// 通用接口: 后插操作
int InsertNextLNode(LNode *n, int e) {
    if (n == NULL) return -1;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return -1;
    s->next = n->next;
    n->next = s;
    s->data = e;
    return 1;
}

// 通用接口: 删除操作
int DeleteLNode(LNode *n, int *e) {
    if (n == NULL) return -1;
    LNode *q = n->next;
    if (q == NULL) return -1;
    n->next = q->next;
    *e = n->data;
    n->data = q->data;
    free(q);
    return 1;
}

// 带头结点的单链表头插
int ListHeadInsert(LinkList l) {
    int x;
    scanf("%i", &x);
    LNode *s = NULL;
    while (x != 999) {
        s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) return -1;
        s->next = l->next;
        l->next = s;
        s->data = x;
        scanf("%i", &x);
    }
    return 1;
}

// 带头结点的单链表尾插
int ListTailInsert(LinkList l) {
    int x;
    LNode *s, *r = l;
    scanf("%i", &x);
    while (x != 999) {
        s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) return -1;
        r->next = s;
        s->data = x;
        r = s;
        scanf("%i", &x);
    }
    r->next = NULL;
    return 1;
}

// 不带头结点的单链表头插
int ListHeadInsert1(LinkList *l) {
    int x;
    scanf("%i", &x);
    while (x != 999) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) return -1;
        s->data = x;
        s->next = *l;
        *l = s;
        scanf("%i", &x);
    }
    return 1;
}

// 不带头结点的单链表尾插
int ListTailInsert1(LinkList *l) {
    int x;
    scanf("%i", &x);
    LNode *r = *l;
    while (x != 999) {
        if (*l == NULL) {
            LNode *s = (LNode *)malloc(sizeof(LNode));
            if (s == NULL) return -1;
            s->data = x;
            r = s;
            *l = s;
        } else {
            LNode *s = (LNode *)malloc(sizeof(LNode));
            if (s == NULL) return -1;
            r->next = s;
            s->data = x;
            r = s;
        }
        scanf("%i", &x);
    }
    r->next = NULL;
    return 1;
}

// 不带头结点的单链表逆置
void ListInverse(LinkList *l) {
    LNode *prev = NULL;
    LNode *curr = *l;
    while (curr != NULL) {
        LNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *l = prev;
}

// 分割线
void Sep() {
    printf("**************\n");
}

int main() {
    LinkList l = InitList1();
    ListTailInsert1(&l);
    ListPrintf(l);
}

void Head() {
    LinkList l = InitList();
    ListInsert(l, 1, 1);
    ListInsert(l, 2, 2);
    ListInsert(l, 3, 6);
    ListInsert(l, 3, 5);
    ListInsert(l, 4, 100);
    ListPrintf(l->next);
    Sep();
    int e = -1;
    ListDelete(l, 3, &e);
    printf("%i\n", e);
    Sep();
    printf("%i\n", Length(l->next));
    Sep();
    printf("%i\n", LocateElem(l->next, 1)->data);
    Sep();
    ListPrintf(l->next);
    Sep();
    printf("%i\n", GetElem(l->next, 4-1)->data);
}

void NoHead() {
    LinkList l = InitList1();
    ListInsert1(&l, 1, 99);
    ListInsert1(&l, 2, 123);
    ListInsert1(&l, 1, 18);
    ListPrintf(l);
    int e = -1;
    ListDelete1(&l, 3, &e);
    Sep();
    printf("%i\n", e);
    Sep();
    ListPrintf(l);
    Sep();
    DestroyList(&l);
    printf("%i\n", Empty(l));
}