一. 线性表的链式存储

线性表的链式存储又称单链表，为了建立数据元素之间的链式关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

为了操作的方便，通常会在单链表第一个结点之前附加一个结点，称为头结点，头节点的数据域可以不设任何信息。

1.1 单链表的基本操作

头插法建立单链表

headInsert

采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的

尾插法建立单链表

tailInsert

销毁单链表

destoryLinkList

输出，按前后顺序输出单链表中的所有元素值

printLinkList

求表长操作，计算单链表中数据结点的个数，不包含头结点

length

按序号查找结点，返回该结点的指针；头结点的序号为 0

getElemByPos

按值查找表结点，返回该结点的指针

getElemByValue

插入结点，将值为 value 的新结点插入到单链表的第 i 个位置上

insertByPos

删除结点，将单链表的第 i 个结点删除

deleteByPos

1.2 基本操作的实现

下列基本操作的实现中，单链表均带头结点

LinkNode *headInsert(int *data, int size){
    LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode));
    head->next = NULL;
    for(int i = 0; i < size; ++i){
        LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
        node->data = data[i];
        node->next = head->next;
        head->next = node;
    }
    return head;
}

int destoryLinkList(LinkNode *head){
    if(head == NULL)
        return -1;
    LinkNode *cur_node = head->next;
    LinkNode *next_node = NULL;
    while(cur_node != NULL){
        next_node = cur_node->next;
        free(cur_node);
        cur_node = next_node;
    }
    free(head);
    return 0;
}

void printLinkList(LinkNode *head){
    LinkNode *cur_node = head->next;
    while(cur_node != NULL){
        printf("%d ", cur_node->data);
        cur_node = cur_node->next;
    }
    printf("\n");
}

LinkNode *tailInsert(int *data, int size){
    LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode));
    head->next = NULL;
    LinkNode *tail_node = head;
    LinkNode *node = NULL;
    for(int i = 0; i < size; ++i){
        node = (LinkNode *)malloc(sizeof(LinkNode));
        node->data = data[i];
        tail_node->next = node;
        tail_node = node;
    }
    tail_node->next = NULL;
    return head;
}

int length(LinkNode *head){
    int length = 0;
    LinkNode *cur_node = head->next;
    while(cur_node != NULL){
        ++length;
        cur_node = cur_node->next;
    }
    return length;
}

LinkNode *getElemByPos(LinkNode *head, int pos){
    if(pos < 0 || pos > length(head))
        return NULL;
    if(pos == 0)
        return head;
    LinkNode *cur_node = head->next;
    while(--pos){
        cur_node = cur_node->next;
    }
    return cur_node;
}

LinkNode *getElemByValue(LinkNode *head, int value){
    LinkNode *cur_node = head->next;
    while(cur_node != NULL){
        if(cur_node->data == value)
            return cur_node;
        cur_node = cur_node->next;
    }
    return NULL;
}

int insertByPos(LinkNode *head, int pos, int value){
    if(pos < 1 || pos > (length(head) + 1))
        return -1;
    LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
    node->data = value;
    LinkNode *cur_node = getElemByPos(head, pos-1);
    node->next = cur_node->next;
    cur_node->next = node;
    return 0;
}

int deleteByPos(LinkNode *head, int pos){
    if(pos < 1 || pos > length(head))
        return -1;
    LinkNode *cur_node = getElemByPos(head, pos-1);
    LinkNode *del_node = cur_node->next;
    cur_node->next = del_node->next;
    free(del_node);
    return 0;
}

作业

1. 反转一个单链表

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

2. 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 2->1->4->3->5->NULL

3. 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

4. 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

5. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

6. 删除链表中等于给定值 val 的所有节点

一. 线性表的链式存储#

1.1 单链表的基本操作#

1.2 基本操作的实现#

作业#

一. 线性表的链式存储

1.1 单链表的基本操作

1.2 基本操作的实现

作业