//
// Created by 陈智涛 on 2017/10/12.
//
#include <stdio.h>
#include <stdlib.h>
typedef int DateType;
typedef struct Node{
    DateType data;
    struct Node * pNextNode;

}NODE,*PNODE;

//初始化
PNODE initNodeList()
{
    //为链表分配一个头结点
    PNODE phead = (PNODE)malloc(sizeof(NODE));
    if(phead == NULL)
    {
        printf("内存分配失败\n");
        exit(-1);
    }
    phead->data = 0;
    phead->pNextNode = NULL;
    return phead;

}
//尾插法插入节点,成功返回1
int appendNode(DateType value,PNODE phead)
{
    if(phead == NULL)
    {
        printf("传入的节点不存在\n");
        exit(-1);
    }
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew == NULL)
    {
        printf("内存分配失败\n");
        exit(-1);
    }
    pNew->data = value;
    pNew->pNextNode = NULL;
    PNODE p = phead;
    while (p->pNextNode)
    {
        p = p->pNextNode;
    }
    p->pNextNode = pNew;

    return 1;

}
void printNodeList(PNODE phead)
{
    PNODE p = phead->pNextNode;
    while (p)
    {

        printf("%d\t",p->data);
        p = p->pNextNode;

    }
    printf("\n");
    return;
}
int getLength(PNODE pnode)
{
    PNODE p = pnode->pNextNode;
    int len = 0;
    while(p)
    {
        len++;
        p = p->pNextNode;
    }
    return len;
}
//将元素插入第i个位置。成功返回该元素的指针
PNODE insertNode(int i,DateType value,PNODE phead)
{
    if(NULL == phead)
    {
        printf("头结点不存在\n");
        return 0;
    }
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew)
    {
        printf("内存申请失败\n");
        exit(-1);
    }
    pNew->data = value;
    int j = 0;
    PNODE p = phead;
    while(p && j < i)
    {
        p = p->pNextNode;
        j++;
    }
    if( j<=i && NULL == p->pNextNode)
    {
        printf("插入的下标超过范围\n");
        free(pNew);
        pNew = NULL;
        return NULL;

    }
    pNew->pNextNode = p->pNextNode;
    p->pNextNode = pNew;
    return pNew;

}
//判断链表是否有环,有环返回1,无环返回0
int isExistsLoop(PNODE phead)
{
    PNODE slow = phead;
    PNODE fast = phead;
    while (fast && fast->pNextNode)
    {
        slow = slow->pNextNode;
        fast = fast->pNextNode->pNextNode;
        if(slow == fast)
            break;
    }
    if(NULL == fast || NULL == fast->pNextNode)
    {
        return 0;
    } else{
        return 1;
    }
}
int main(void)
{
    //初始化
    PNODE phead = initNodeList();
    //尾部插入
    for (int i = 0; i < 10; ++i) {
        appendNode(i,phead);
    }

    printNodeList(phead);

    //i位置插入
    PNODE val = insertNode(10,99,phead);
    if(NULL == val){
        printf("插入失败\n");
    }else{
        printf("被插入的值是%d\n",val->data);
    }

    printNodeList(phead);

    //判断链表是否有环
    int isLoop = 0;
    isLoop = isExistsLoop(phead);
    printf("检查是否有环1存在,0不存在:%d\n",isLoop);
    return 0;
}