本文共 8365 字，大约阅读时间需要 27 分钟。

学习一种数据结构，要注意：逻辑结构、存储结构、相关操作。

链表最好带一个头结点。

链表的创建一般是在堆上的。

特别注意！！！

• 进行遍历的时候，结束条件是(p != NULL)，因为循环里面会执行p = p->next;，所以判断时候的p实际上是结点的next指针
• 寻找前驱结点的时候要判断-1的情况，直接返回H，然后就是一个for (i = 0; i < post; i++)来遍历（从p = H开始），到时候直接返回p！注意是p从头结点指针开始！
• 尾部插入时，遍历判断的条件是(p->next != NHULL)，这样，p才是指向尾结点的，而不是尾结点的上一个结点指针
• 删除单个结点的时候要注意，不能截断整个链表，所以要单独一个指针指向删除的结点，先将这个结点移出链表，再进行单独释放
• 记得在使用完之后释放整个链表，可以在释放的时候打印一下结点信息

1.创建

对于创建一个链表，首先创建一个头结点H。

在堆中创建链表，注意每创建一个节点的时候，对其进行初始化更为严谨，因为这个时候节点还没有与链表建立联系。

创建完成之后，返回这段空间的地址，再往下讲，创建一个空节点就相当于在堆中申请一段listnode大小的空间地址，所以返回的也就是这段地址了。

linklist list_create(void){
           linklist p = (linklist)malloc(sizeof(listnode));            	if (p == NULL) {
                   puts("linklist is NULL!");                return NULL;        }                   p->data = 0;        p->next = NULL;        return p;}

2.遍历

传入链表的头结点，通过头结点将所有节点的数据打印出来。

int list_show(linklist H){
           linklist p = H->next;                    if (p == NULL) {
                   puts("H is NULL");                return 0;        }                   printf("H->");        for (; p != NULL;) {
                   printf("%d->", p->data);                p = p->next;        }                   puts("NULL");        return 1;}

注意，在遍历的时候，p = p->next判断，相当于当前判断的p是上一个p

3.插入

3.1尾部插入

int list_tail_insert(linklist H, data_t val){
           int i;        linklist last = list_create();        linklist p = H;        while (p->next != NULL) {
    //遍历到尾部前一个                p = p->next;        }        p->next = last;  //尾部插入        last->data = val;        last->next = NULL;        return 1;}

3.2指定位置插入

/* *在post位置之前插入新节点，也就是新的节点代替原节点，称为第post节点 *post的位置从0开始 * */int list_post_insert(linklist H, int post, data_t val){
   	if (H == NULL) {
   		puts("H is NULL");		return -1;	}	linklist p = list_prev_find(H, post);	linklist new = (linklist)malloc(sizeof(listnode));	if (new == NULL) {
   		puts("new node malloc filed");		return -1;	}	new->data = val;	new->next = p->next;	p->next = new;	return 0;}

4.查找

/* *寻找返回post位置的前驱节点 *post位置从零开始 * */linklist list_prev_find(linklist H, int post){
   	int i;	linklist p;	if (H == NULL) {
   		puts("H is NULL");		return NULL;	}	if (post == -1) return H;	if (post < -1) {
   		puts("post insert is err");		return NULL;	}	p = H;	for (i = 0; i < post; i++) {
     //找到post前一个节点		if (p->next == NULL) {
   			puts("post insert is err");			return NULL;		}		p = p->next;	}	return p;}

5.删除

int list_delete(linklist H, int post){
   	linklist p, q;	if (H == NULL) {
   		puts("H is NULL");		return -1;	}	p = list_prev_find(H, post);	q = p->next;	p->next = q->next;	free(q);	q = NULL;	return 0;}

6.释放

int list_free(linklist H){
   	if (H == NULL) return -1;	linklist p = H;	puts("free:");	while (H != NULL) {
   		p = H;		printf("%d ", H->data);		H = H->next;		free(p);	}	puts("");	return 0;}

7.排序

细节：

• 截断链表，p指针指向截断部分
• 对截断部分排序，每次找出最小的结点
• 在H后面利用另外一个指针r来执行插入操作

8.倒置、反转

不允许出现malloc、free！！！

所以要申请一个新的头结点来指向后面的链表，这样就相当于转换为两个链表的插入问题了。

细节：

• 注意空链表和单个结点的处理，还有当头结点为NULL时的情况
• 将链表一分为二，新的结点指针指向后面的部分，然后再断开原链表
• 将后面的链表遍历插入到原链表的0位置（也就是第一个结点的位置）
• 在插入的时候，对于后半部分的链表，可以借助另外一个指针来遍历

代码：

int list_inversion(linklist H){
           linklist p, q;        if (H == NULL) {
                   puts("H si NULL!");                return -1;        }        if ((H->next == NULL) || (H->next->next == NULL)) return 0;                p = H->next->next;     //p指向后半部分        H->next->next = NULL;  //断开H，只留原始0位置的结点        while (p != NULL) {
                   q = p;                p = p->next;   //遍历后半部分链表                q->next = H->next; //始终插入到0位置                H->next = q;        }        return 0;}

9.求相邻两结点最大值

细节：

• 注意H为NULL的特殊情况
• 只有一个结点、两个结点时的特殊情况
• 返回的是一个结点指针linklist
• 注意遍历的结束条件，后一个结点是最后一个结点的时候
• 要有一个结点指针来存储max结点的地址
• 在取到地址之后还要做判断

代码：

linklist list_adjmax(linklist H){
           linklist p, q, r;        int tmp = 0, max = 0;        if (H == NULL) {
                   puts("H is NULL!");                return NULL;        }        if ((H->next == NULL) ||             (H->next->next == NULL) ||             (H->next->next->next == NULL)) return H->next;        p = H->next;        q = p->next;        r = p;        while (q != NULL) {
                 //遍历                tmp = p->data + q->data; //计算当前值                r = max>tmp?r:p;         //取较大的结点组的第一个结点的地址                max = max>tmp?max:tmp;   //更新max                                p = p->next;                q = q->next;        }                return r;}

10.合并两有序链表

细节：

• 两个链表，由两个结点指针断开
• 相当于是两个结点指针进行比较，小的插入H1中
• 插入都是尾部插入，由另外一个结点指针负责插入操作

核心思想是分隔原链表，用一个结点指针来执行插入操作。

代码：

int list_merge(linklist H1, linklist H2){
           linklist p, q, r;        if ((H1 == NULL) || (H2 == NULL)) {
                   puts("H is NULL!");                return -1;        }        p = H1->next;        q = H2->next;        r = H1;        H1->next = NULL;        H2->next = NULL;        while (p && q) {
                   if (p->data < q->data) {
                           r->next = p;                        p = p->next;                        r = r->next;                        r->next = NULL;                } else {
                           r->next = q;                        q = q->next;                        r = r->next;                        r->next = NULL;                }        }        if (p == NULL) {
                   r->next = q;        } else {
                   r->next = p;        }        return 0;}

递归代码：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
       if(l1==NULL)        return l2;    if(l2==NULL)        return l1;    if(l1->val < l2->val){
           l1->next = mergeTwoLists(l1->next,l2);        return l1;    }else{
           l2->next = mergeTwoLists(l1,l2->next);        return l2;    }}

11. 反向递归遍历

给出一个单向不循环链表的头结点，要求不改变链表结构的情况下反向遍历链表中的元素。

思路：递归实现，判断p是否为空，来输出元素。

#include 
   
    #include 
    
     #include 
     
      typedef int data_t;typedef struct node {
       data_t data;    struct node *next;}node;node *list_create();int list_show(node *H);node *list_pre_find(node *H, int post);int list_insert_post(node *H, int post, data_t val);int list_delete(node *H, int post);int list_free(node *H);int list_reverse_show(node *H);int main(int argc, const char *argv[]){
       int i, n, num;    printf("input num size :");    scanf("%d", &n);     node *H = list_create();    printf("intput data:");    for (i = 0; i < n; i++) {
           scanf("%d", &num);        list_insert_post(H, i, num);    }    list_show(H);    /* 功能测试 */    list_delete(H, 0);    list_show(H);    list_insert_post(H, 0, 99);    list_show(H);    /* 递归反向遍历，不打印头结点数据，所以传入 H->next */    list_reverse_show(H->next);    puts("");    list_free(H);    return 0;}int list_reverse_show(node *H){
       node *p = H;    if (p != NULL) {
           list_reverse_show(p->next);  //陷入递归，直到链表末尾开始返回，逐步执行printf        printf("%d ", p->data);    }    return 0;}node *list_create(){
       node *p = (node*)malloc(sizeof(node));    if (NULL == p) {
           printf("malloc filed\n");        return NULL;    }    memset(p, 0, sizeof(node));    p->next = NULL;    return p;}int list_show(node *H){
       if (NULL == H) {
           printf("H is NULL\n");        return -1;    }    node *p = H;    printf("H->");    while (p->next != NULL) {
           p = p->next;        printf("%d->", p->data);            }    printf("NULL\n");    return 0;}node *list_pre_find(node *H, int post){
       if (NULL == H) {
           printf("H is NULL\n");        return NULL;    }    int i;    node *p;    p = H;    for (i = 0; i < post; i++) {
           if (NULL == p) {
               printf("post is over!\n");            return NULL;        }        p = p->next;    }    return p;}int list_insert_post(node *H, int post, data_t val){
       if (NULL == H) {
           printf("H is NULL\n");        return -1;    }    node *p, *q;    p = list_create();    p->data = val;    q = list_pre_find(H, post);    p->next = q->next;    q->next = p;    return 0;}int list_delete(node *H, int post){
       if (NULL == H) {
           printf("H is NULL\n");        return -1;    }    node *p = list_pre_find(H, post);    node *q;    q = p->next;    p->next = q->next;    free(q);    q = NULL;    return 0;}int list_free(node *H){
       if (NULL == H) {
           printf("H is NULL\n");        return -1;    }    node *p = H;    node *q;    while (p != NULL) {
           q = p;        p = p->next;        free(q);    }    q = NULL;    return 0;}
     
    
   

转载地址：http://vtwzi.baihongyu.com/