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

typedef int ElemType;

/*定义结构体*/
typedef struct LNode
{
    struct LNode *next;
    ElemType num;
}LNode;

/*链表初始化*/
void initList(LNode ** head)
{
    if((*head = (LNode *)malloc(sizeof(LNode))) != NULL)
    {
        (*head)->next = NULL;
    }
}

/*求链表中元素的个数*/
int ListLength(LNode *head)
{
    int length = 0;
    /*指针p指向头节点*/
    LNode *p = head;
    while(p->next != NULL)
    {
        length += 1;
        p = p->next;
    }
    
    return length;
}
/*插入成功return 1,失败return 0*/
/*i代表第i个元素后插入节点，节点num为x*/
int ListInsert(LNode *head,int i,ElemType x)
{
    LNode *p,*q;
    p = head;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j += 1;
    }
    /*插入位置非法*/
    if(j!=i-1)
        return 0;
    if((q = (LNode *)malloc(sizeof(LNode))) == NULL)
    {
        /*分配内存失败*/
        printf("Malloc memory failed.\n");
        return 0;
    }
    /*x赋值*/
    q->num = x;
    
    /*插入到正确位置*/
    q->next = p->next;
    p->next = q;
    /*插入成功*/
    return 1;
}
/*删除链表中第i+1个元素，x保存删除节点的num*/
int ListDel(LNode *head,int i,ElemType *x)
{
    LNode *p = head;
    LNode *s = NULL;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j++;
    }
    
    /*插入位置非法*/
    if(j != i-1)
        return 0;
    
    /*s指向待删元素*/
    s = p->next;
    /*待删除元素由x带回*/
    *x = s->num;
    p->next = p->next->next;
    
    /*释放待删除元素*/
    free(s);
    s = NULL;
    return 1;
}

/*销毁整个链表*/
void destoryList(LNode *head)
{
    if(head == NULL)
        return;
    
    LNode *p = head;
    LNode *s = NULL;
    
    while(p->next != NULL)
    {
        s = p->next;
        p->next = p->next->next;
        free(s);
        s = NULL;
    }
    
}

/*打印链表中的全部元素*/
void printList(LNode *head)
{
    if(head == NULL)
        return;
    
    if(ListLength(head) == 0)
    {
        printf("Empty!\n");
    }
    /*每10个元素打印一行*/
    int cnt = 0;
    LNode *p = head;
    while(p->next != NULL)
    {
        p = p->next;
        printf("%d ",p->num);
        if(cnt % 9 == 0)
            printf("\n");
    }
    
}

/*函数用于验证链表基本操作是否正确*/
void checkListValid()
{
    LNode *head = NULL;
    ElemType x = 0;
    /*链表初始化*/
    initList(&head);
    if(head == NULL)
        printf("Error.\n");
    
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    destoryList(head);
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    
    /*链表中无元素，删除元素非法*/
    if(ListDel(head,1,&x) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }

    printList(head);
    
    /*删除10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(1 != ListDel(head, 0, &x)|| (x != i+1))
            printf("Error.\n");
    }
    printList(head);
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    /*删除第4个元素，num为4*/
    if(1 != ListDel(head, 3, &x)|| (x != 4))
        printf("Error.\n");
    
    /*插入元素4，位置4*/
    if(0 == ListInsert(head, 3, 4))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*删除最后一个元素*/
    if(1 != ListDel(head, 9, &x)|| (x != 10))
        printf("Error.\n");
    
    /*删除最后一个元素8*/
    if(1 != ListDel(head, 8, &x)|| (x != 9))
        printf("Error.\n");
    
    /*删除第三个元素3*/
    if(1 != ListDel(head, 2, &x)|| (x != 3))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*销毁链表*/
    destoryList(head);
    
    printf("\n");
    printList(head);
}

/*找出单链表中倒数第k个节点*/
LNode * nthToLast(LNode *head,int k)
{
    LNode *ans = head;
    LNode *end = head;
    /*k小于0或链表长度小于k犯错*/
    if((k<= 0)||(ListLength(head)<k))
        return NULL;
    /*让end向前移动k个节点*/
    for(int i = 0;i < k-1;i++)
    {
        /*此处应该不用判断，因为前面有判断链表长度*/
        if(end == NULL)
            return NULL;
        end = end->next;
    }
    /*end指向最后时，ans恰好指向倒数第k个结点*/
    while((ans->next != NULL)&&(end->next != NULL))
    {
        ans = ans->next;
        end = end->next;
    }
    
    return ans;
}

/*删除单链表中第k个结点，限制条件只能访问第k个结点，不能删除第k个结点*/
bool deleteNode(LNode *head,int k)
{
    if((NULL == head)||(head->next == NULL))
        return false;
    /*指向要删除的结点*/
    LNode *ans = head;
    LNode *ans_next = head->next;
    int len = ListLength(head);
    /*长度不符合限制返回false*/
    if((k <= 0)||(k>len))
        return false;
    /*区分是否删除最后一个结点，如果删除最后一个结点，则只用置ans->next = NULL*/
    while(k>0 &&(ans->next != NULL)&&(ans_next->next != NULL))
    {
        ans = ans->next;
        ans_next = ans_next->next;
        k -= 1;
    }
    
    if(k == 0)
    {
        /*删除结点不是最后一个结点，将后一个结点的内容拷贝到ans->num,删除ans_next*/
        ans->num = ans_next->num;
        ans->next = ans_next->next;
        free(ans_next);
        ans_next = NULL;
    }
    else
    {
        /*删除的是最后一个元素*/
        free(ans_next);
        ans->next = NULL;
    }
    return true;
    
}
/*将链表中的结点重新排序，小于x的在前，大于等于x的在后*/
LNode * partition(LNode *head,ElemType x)
{
    if((head == NULL)||(head->next == NULL))
        return NULL;
    LNode *last = NULL;
    LNode * p = head->next;
    /*初始化两个链表*/
    LNode * small = NULL;
    LNode * big = NULL;
    initList(&small);
    initList(&big);
    while(p != NULL)
    {
        if(p->num < x)
            ListInsert(small,0,p->num);
        else
            ListInsert(big,0,p->num);
        p = p->next;
    }
    
    destoryList(head);
    last = small;
    /*找到small链表中最小元素*/
    while(last->next != NULL)
        last = last->next;
    last->next = big->next;
    free(big);
    
    return small;
}
int main(int argc, const char * argv[])
{
    
    //checkListValid();
    LNode *head = NULL;
    /*链表初始化*/
    initList(&head);
    ListLength(head);
    /*插入10个元素*/
    ListInsert(head, 0, 10);
    ListInsert(head, 1, 8);
    ListInsert(head, 2, 7);
    ListInsert(head, 3, 1);
    ListInsert(head, 4, 2);
    ListInsert(head, 5, 6);
    ListInsert(head, 6, 5);
    ListInsert(head, 7, 4);
    ListInsert(head, 8, 3);
    ListInsert(head, 9, 9);
    
    LNode *par = partition(head,5);
    printList(par);
    destoryList(par);
    return 0;
}