/**
 * @author shuang
 * @for kun
 */

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

typedef int ElemType;

typedef struct LNode {
    ElemType val;
    struct LNode *next;
} LNode, *LinkList;

void construct_link_list(LinkList *list, bool with_head, int range);

void traverse_link_list(LinkList *list);

bool insert_with_head(LinkList *list, int index, ElemType val);

bool insert_without_head(LinkList *list, int index, ElemType val);

int main() {
    LinkList list_with_head, list_without_head;
    construct_link_list(&list_with_head, 1, 10);
    construct_link_list(&list_without_head, 0, 10);
    traverse_link_list(&list_with_head);
    traverse_link_list(&list_without_head);
    putchar(10); // 输出换行符
    insert_with_head(&list_with_head, 1, 10);
    insert_without_head(&list_without_head, 1, 10);
    traverse_link_list(&list_with_head);
    traverse_link_list(&list_without_head);

    return 0;
}

/**
 * 构建一个单链表
 * @param list 链表指针, 传入时应为NULL, 此处为C的引用方式, 即指针的指针, 要调用的时候前面加*即可取值
 * @param with_head 创建的链表是否要带头结点
 */
void construct_link_list(LinkList *list, bool with_head, int range) { // 构建一个单链表
    LinkList val_start_node, val_end_node, node;

    node = (LinkList) malloc(sizeof(LNode));
    node->val = 0;
    val_start_node = node;
    val_end_node = node;
    for (int i = 1; i < range; i++) {
        node = (LinkList) malloc(sizeof(LNode));
        node->val = i;
        node->next = NULL;
        val_end_node->next = node;
        val_end_node = node;
    }

    if (with_head) {
        LinkList head = (LinkList) malloc(sizeof(LNode));
        head->val = -1;
        *list = head;
        head->next = val_start_node;
    } else {
        *list = val_start_node;
    }

}

/**
 * 遍历单链表并依次输出结点值
 * @param list 链表指针, 此处为C的引用方式, 即指针的指针, 要调用的时候前面加*即可取值
 */
void traverse_link_list(LinkList *list) {
    LinkList iter = *list;
    while (iter != NULL) {
        if (iter->val == -1) {
            iter = iter->next;
            continue;
        }
        printf("%d ", iter->val);
        iter = iter->next;
    }
    putchar(10);
}

/**
 * 向带头结点的单链表中插入一个新的结点
 * @param list 链表指针, 此处为C的引用方式, 即指针的指针, 要调用的时候前面加*即可取值
 * @param index 要插入的结点最终在链表中的位置, 以1为起始
 * @param val 要插入的结点的值
 * @return 插入是否成功
 */
bool insert_with_head(LinkList *list, int index, ElemType val) {
    if (*list == NULL) { // 没有头结点不能插入
        return false;
    }
    LinkList iter = *list; // iter: 迭代器, 用来遍历链表的指针
    int j = 0;
    while (iter != NULL && j < index - 1) { // 找到第i-1个结点, 即j = i-1时iter指向的结点
        iter = iter->next;
        j++;
    }
    if (iter == NULL) { // 链表长度不足index - 1
        return false;
    }
    LinkList node = (LinkList) malloc(sizeof(LNode));
    node->val = val;
    node->next = iter->next; // 先给新结点设置尾指针, 否则覆盖iter的尾指针后会丢失
    iter->next = node;
    return true;
}

/**
 * 向不带头结点的单链表中插入一个新的结点
 * @param list 链表指针, 此处为C的引用方式, 即指针的指针, 要调用的时候前面加*即可取值
 * @param index 要插入的结点最终在链表中的位置, 以1为起始
 * @param val 要插入的结点的值
 * @return 插入是否成功
 */
bool insert_without_head(LinkList *list, int index, ElemType val) {
    if (index == 1) { // 直接向头指针后插入的情况
        LinkList node = (LinkList) malloc(sizeof(LNode));
        node->val = val;
        node->next = *list;
        *list = node;
        return true;
    }

    LinkList iter = *list; // iter: 迭代器, 用来遍历链表的指针
    int j = 1;
    while (iter != NULL && j < index - 1) { // 找到第i-1个结点, 即j = i-1时iter指向的结点
        iter = iter->next;
        j++;
    }
    if (iter == NULL) { // 链表长度不足index - 1
        return false;
    }
    LinkList node = (LinkList) malloc(sizeof(LNode)); // 先给新结点设置尾指针, 否则覆盖iter的尾指针后会丢失
    node->val = val;
    node->next = iter->next;
    iter->next = node;
    return true;
}

/**
 * 执行结果
 * 0 1 2 3 4 5 6 7 8 9
 * 0 1 2 3 4 5 6 7 8 9
 *
 * 10 0 1 2 3 4 5 6 7 8 9
 * 10 0 1 2 3 4 5 6 7 8 9
 */