#include <stdio.h>

#include <stdlib.h>

struct node{
    
    int data;
    
    struct node *next;
    
}*head;

void setupNullList();//创建一个空链表

void insertTailList();//尾插链表

void insertHeadList();//头插链表

struct node *creatNode();//创建一个结点

void appendNode(struct node *n);//追加结点

void insertNode(struct node *n);//插入结点

void deleteNode();//删除结点

void updateNode();//修改结点

void reverseList();//链表逆序

void showList();//输出链表

int listType = 0;

int main(){
    setupNullList();
    system("clear");
    printf("\n1、头插链表\n\n2、尾插链表\n\n请选择:\n\n");
    int flag = 0;
    scanf("%d",&flag);
    switch(flag){
        case 1:{
            listType = 1;
            insertHeadList();
            break;
        }
        case 2:{
            listType = 2;
            insertTailList();
            break;
        }
        default:
            break;
    }
    showList();
    flag = 1;
    int flagExit = 0;
    while(flag){
        printf("\n1、追加结点\n\n2、插入结点\n\n3、删除结点\n\n4、修改结点\n\n5、链表逆序\n\n6、输出链表\n\n0、退出程序\n\n请选择：\n\n");
        scanf("%d",&flag);
        switch(flag){
            case 1:{
                struct node *n = creatNode();
                if(NULL != n){
                    appendNode(n);
                }
                break;
            }
            case 2:{
                struct node *n = creatNode();
                if(NULL != n){
                    insertNode(n);
                }
                break;
            }
            case 3:{
                deleteNode();
                break;
            }
            case 4:{
                updateNode();
                break;
            }
            case 5:{
                reverseList();
                break;
            }
            case 6:{
                showList();
                break;
            }
            case 0:{
                flagExit = 1;
                break;
            }
        }
        if(flagExit == 1) break;
    }
    return 0;
    
}

//创建一个空链表
void setupNullList(){
    head = (struct node *)malloc(sizeof(struct node));
    if(NULL == head){
        printf("链表创建失败!\n");
    }else{
        head->next = NULL;
        head->data = 0;
    }
}

//尾插链表
void insertTailList(){
    struct node *tail = NULL;//尾结点
    printf("\n请输入要创建的结点id,输入0结束\n\n");
    int number = 0;
    scanf("%d",&number);
    while(number != 0){
        struct node *n = (struct node *)malloc(sizeof(struct node));
        n->data = number;
        n->next = NULL;
        if(head->next == NULL){//第一个结点
            head->next = n;
        }else{
            tail->next = n;
        }
        tail = n;
        scanf("%d",&number);
    }
}

//头插链表
void insertHeadList(){
    printf("\n请输入要创建的结点id,输入0结束\n\n");
    int number = 0;
    scanf("%d",&number);
    while(0 != number){
        struct node *n = (struct node *)malloc(sizeof(struct node));
        n->data = number;
        n->next = head->next;
        head->next = n;
        scanf("%d",&number);
    }
}

//创建结点
struct node *creatNode(){
    struct node *n = (struct node *)malloc(sizeof(struct node));
    printf("请输入要创建的结点id\n\n");
    int number = 0;
    scanf("%d",&number);
    if(NULL != n){
        n->data = number;
        n->next = NULL;
    }
    return n;
}

//在表尾追加结点
void appendNode(struct node *n){
    struct node *p = head->next;
    while(NULL != p->next){
        p = p->next;
    }
    p->next = n;
}

//插入结点
void insertNode(struct node *n){
    struct node *before = head;
    struct node *p = head->next;
    while(NULL != p){
        if(listType == 1 && p->data < n->data){
            before->next = n;
            n->next = p;
            break;
        }else if(listType == 2 && p->data > n->data){
            before->next = n;
            n->next = p;
            break;
        }else{
            break;
        }
        before = p;
        p = p->next;
    }
    if(p == NULL){
        before->next = n;
    }
}

//删除节点
void deleteNode(){
    printf("\n请输入要删除的结点id\n\n");
    int number = 0;
    scanf("%d",&number);
    struct node *before = head;
    struct node *p = head->next;
    while(NULL != p){
        if(p->data == number){
            before->next = p->next;
            free(p);
            break;
        }
        before = p;
        p = p->next;
    }
}

//更新结点
void updateNode(){
    int oldNumber = 0;
    int newNumber = 0;
    printf("\n请输入要修改的结点id\n\n");
    scanf("%d",&oldNumber);
    printf("\n请输入新的结点id\n\n");
    scanf("%d",&newNumber);
    struct node *p = head->next;
    while(NULL != p){
        if(p->data == oldNumber){
            p->data = newNumber;
        }
        p = p->next;
    }
}

//链表逆序
void reverseList(){
    struct node *p = head->next;
    struct node *q = NULL;
    head->next = NULL;
    while(NULL != p){
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

//输出链表
void showList(){
    system("clear");
    struct node *p = head->next;
    while(NULL != p){
        if(NULL != p->next){
            printf("%d -> ",p->data);
        }else{
            printf("%d\n",p->data);
        }
        p = p->next;
    }
}