/* 单向链表操作集 */
#include<stdio.h>
#include<stdlib.h>

#define ERROR NULL
typedef int ElementType;
typedef struct LNode *List;
struct LNode{
    ElementType Data;
    List Next;
};
struct LNode L;
List PtrL;

List CreatList(); //建立链表
ElementType Length(List L); //求表长
ElementType FindK(ElementType K,List L); //查找第K个节点
List FindX(ElementType X,List L); //查找元素X
List Insert(ElementType X,ElementType i,List L);//插入新节点
List Delete(ElementType i,List L);  //删除第i个节点
List Reverse(List L); //链表的反转
void Show(List L); //输出链表
void FreeMemory(List L); //内存释放

int main()
{
    PtrL = CreatList();
    Show(PtrL);
    FreeMemory(PtrL);

    getchar();
    getchar();
    return 0;
}

/* 尾插法建立链表 */
List CreatList()
{
    List head = NULL;
    List current;
    List prev = NULL;
    int len = 0;

    printf("pleasr enter the length of the list:\n");
    scanf_s("%d", &len);

    if (len == 0)   return NULL;

    while (len--) {
        current = (List)malloc(sizeof(struct LNode));
        if (head == NULL)
            head = current;
        else
            prev->Next = current;
        current->Next = NULL;
        scanf_s("%d", &current->Data);
        prev = current;
    }
    return head;
}

/* 输出链表 */
void Show(List L)
{
    List current = L;

    if (current == NULL)
        printf("NULL");
    else
        printf("the List is:\n");
    while (current != NULL) {
        printf("%d ", current->Data);
        current = current->Next;
    }
}

/* 释放内存 */
void FreeMemory(List L)
{
    List current=L;
    List temp=NULL;
    while(current!=NULL){
        current->Next=temp;
        free(current);
        current=temp;
    }
}

/* 求表长 */
ElementType Length(List L)
{
    List current=L;
    int num=0;
    while(current!=NULL){
        current=current->Next;
        num++;
    }
    return num;
}

/* 按序号查找，查找第K个节点 */
ElementType FindK(ElementType K,List L)
{
    List current=L;
    int num=1;
    while(current!=NULL&&num<K){
        current=current->Next;
        num++;
    }
    if(num==K)  return current->Data;
    else return NULL;
}

/* 按数值查找，查找元素X */
List FindX(ElementType X,List L)
{
    List current=L;
    while(current!=NULL&&current->Data!=X)
        current=current->Next;
    return current;
}

/*
    在第i-1节点的后面插入一个值为X的新节点
    先构造一个新的节点，用temp指向 
    在找到链表的第i-1个节点，用p指向 
    然后修改指针，插入节点（p之后插入新节点是temp）
*/
List Insert(ElementType X,ElementType i,List L)
{
    List temp;
    List current=L;
    ElementType j=0;
    ElementType n=1;

    //插在表头
    if(X==1){
        temp=(List)malloc(sizeof(struct LNode));
        temp->Data=X;
        temp->Next=current;
        return temp;
    }else;

    //插在表中
    while(current!=NULL&&n<i-1){
        current=current->Next;
        n++;
    }
    if(n==i-1){
        temp=(List)malloc(sizeof(struct LNode));
        temp->Data=X;
        temp->Next=current->Next;
        current->Next=temp;

        return L; 
    }
    else
        return NULL;
}

/* 
    删除链表的第i个位置上的节点 
    先找到链表的第i-1节点，用p指向 
    用指针temp指向要被删除的节点（p的下一个节点） 
    修改指针，删除temp所指向的节点 
    释放s所指向的节点的空间 
*/
List Delete(ElementType i,List L)
{
    List temp;
    List p;
    List current=L;
    ElementType j=0;
    ElementType n=1;
    
    //删除节点位于表头
    if(i==1){
        temp=L;
        if(temp!=NULL)
            current=current->Next;
        else return NULL;
        free(temp);
        return current;
    }else;

    //删除节点位于表中
    while(current!=NULL&&n<i-1){
        current=current->Next;
        n++;
    }
    if(n==i-1){
        temp=current->Next;
        current->Next=temp->Next;
        free(temp);

        return L;
    }else   return NULL;

}

/*
    链表的反转
    思路：每次都将原第一个结点之后的那个结点放在新的表头后面。 
    比如head,1,2,3,4,5 
    第一次：把第一个结点1后边的结点2放到新表头后面，变成head,2,1,3,4,5 
    第二次：把第一个结点1后边的结点3放到新表头后面，变成head,3,2,1,4,5 
    …… 
    直到： 第一个结点1，后边没有结点为止。 
*/
List Reverse(List L)
{
    List head;
    List current=L;
    List temp;

    if(current==NULL)   return NULL;

    head=(List)malloc(sizeof(struct LNode));
    head->Next=current;

    while(current->Next!=NULL){
        temp=current->Next; //指向要放在前面的节点
        current->Next=temp->Next; //从表中删除temp节点
        temp->Next=head->Next;  //temp接在head后面
        head->Next=temp;
    }

    return head->Next;
}