#include <cstdio>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;  // 指针
} LNode, *LinkList;  // 意义相同 加强自己理解 - LNode *表示结点 LinkList表示此单链表

/*
// 初始化没有头结点的单链表
bool InitLinkList(LinkList &L)
{
    L = NULL;
    return true;
}

bool isEmpty(LinkList L)
{
    if (L == NULL) return true;
    else return false;
}
*/

// 初始化有头结点的单链表
bool InitLinkList(LinkList &L)
{
    L = (LNode *) malloc(sizeof(LNode));
    if (L == NULL) return false;  // 内存不足 分配失败
    L->next = NULL;
    return true;
}

bool isEmpty(LinkList L)
{
    if (L->next == NULL) return true;
    else return false;
}

// 按位查找(返回第i个元素 带头结点)
LNode* GetElem(LinkList L, int i)
{
    if (i < 0) return NULL;

    LNode *p;
    int j = 0;
    p = L;

    while (p != NULL && j < i)
    {
        p = p->next;
        j ++;
    }

    return p;
}

/*
按位查找(不带头结点)
LNode* GetElem(LinkList L, int i)
{

}
*/

// 按值查找
LNode* LocateElem(LinkList L, int e)
{
    LNode *p = L->next;

    while (p != NULL && p->data != e)
    {
        p = p->next;
    }

    return p; 
}

/*
按值查找(不带头结点)
LNode* LocateElem(LinkList L, int e)
{

}
*/

// 求表长(带头结点)
int Length(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len ++;
    }

    return len;
}

/*
// 求表长(不带头结点)
int Length(LinkList L)
{
    int len = 0;

    if (L == NULL) return 0;

    else
    {
        len = 1;
        LNode *p = L->next;
        while (p != NULL)
        {
            p = p->next;
            len ++;
        }
    }

    return len;
}
*/

// 指定结点的后插操作
bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL) return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;

    s->data = e;
    s->next = p->next;
    p->next = s;

    return true;
}

// 尾插法建立单链表(带头结点)
LinkList ListTailInsert(LinkList &L)
{
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LNode *s, *r = L;  // s为新建结点 r为尾结点

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;

    return L;
}

/*
// 尾插法建立单链表(不带头结点)
LinkList ListTailInsert(LinkList &L)
{
    int x;
    LNode *s, *r = L;

    // 单独对第一个结点特殊处理
    scanf("%d", &x);
    L = (LNode *) malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;
    r = L;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;

    return L;
}
*/

// 头插法建立单链表(带头结点)
LinkList ListHeadInsert(LinkList &L)
{
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LNode *s;
    L->next = NULL;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }

    return L;
}

/*
// 头插法建立单链表(不带头结点)
LinkList ListHeadInsert(LinkList &L)
{
    int x;
    LNode *s;

    scanf("%d", &x);
    L = (LNode *) malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;

    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;
        scanf("%d", &x);
    }

    return L;
}
*/

// 在第i个位置插入值为e的元素
// 如果是不带头结点的需要对第一个元素进行特殊处理
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1) return false;

    // LNode *p = GetElem(L, i - 1);  封装
    LNode *p;  // 指针p指向当前扫描到的结点
    int j = 0;  // j表示当前结点的位序
    p = L;  // 初始位置为头结点

    // 寻找第i-1个位置
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j ++;
    }

    // return InsertNextNode(p, e);  封装

    if (p == NULL) return false;

    // 找到第i个位置后创建新结点
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;


    return true;
}

// 指定结点的前插操作
bool InsertPriorNode(LNode *p, int e)
{
    if (p == NULL) return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;

    s->data = p->data;
    s->next = p->next;
    p->data = e;
    p->next = s;
}

// 按位序删除并且将删除的值返回给e
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1) return false;

    // LNode *p = GetElem(L, i - 1);  封装
    LNode *p;
    int j = 0;
    p = L;

    // 寻找第i-1个位置
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j ++;
    }

    if (p == NULL) return false;
    if (p->next == NULL) return false;

    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);

    return true;
}

// 删除指定结点 - 但如果要删除的结点是最后一个结点则会出现空指针的错误 那样的话就只能从表头开始遍历
bool DeleteNode(LNode *p)
{
    if (p == NULL) return false;

    LNode *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);

    return true;
}

// 带头结点
void PrintList(LinkList L)
{
    if (isEmpty(L)) printf("This LinkList is empty!\n");
    else
    {
        LNode *p = L->next;
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

/*
// 不带头结点
void PrintList(LinkList L)
{
    if (isEmpty(L)) printf("This LinkList is empty!\n");
    else
    {
        LNode *p = L;
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
*/

void test()
{
    LinkList L;
    InitLinkList(L);

    ListTailInsert(L);

    printf("%d\n", Length(L));
    PrintList(L);
}

int main()
{
    test();   

    return 0;
}