链表

本文语法涉及大量C语言中结构体的语法，请在食用前确保已经有所了解，不然可能会一头雾水。

当然，如果实在不懂，可以留言。

一、链表的概念

对于顺序存储的结构，最大的缺点就是 插入 和 删除 的时候需要移动大量的元素。所以基于前人的智慧，他们发明了链表。

1、链表的定义

链表由一个个结点组成，每个结点之间通过链接关系串联起来，每个结点都有一个后继结点，最后一个结点的后继结点为空结点。

由链接关系 A -> B组织起来的两个结点，B 被称为 A 的后继结点，A 被称为 B 的前驱结点。

链表分为单向链表、双向链表、循环链表等等。

本文介绍单向链表。

2、链表结点的定义

1
2
3
4
struct ListNode {
    DataType data; 	// (1)
    ListNode *next; // (2)
};

（1）data 是数据域，用来储存数据，可以是任意类型，由编码的人自行指定其DataType。本文数据域全部采用int型进行讲解。

（2）*next是指针域，指向 后继结点 的地址。

3、链表结点创建

1
2
3
4
5
6
ListNode *ListCreateNode(DataType data) {
    ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); 	// (1)
    node->data = data; 											// (2)
    node->next = NULL; 											// (3)
    return node; 												// (4)
}

（1）利用系统库函数 malloc分配一块内存空间用来存放 ListNode ，即链表结点对象。

（2）将数据域置为函数传参data

（3）将指针域置空，代表这是一个孤立的 链表结点，即没有后继节点。

（4）最后返回这个结点的指针

4、虚拟头结点

为了方便对链表执行操作，往往会建立一个虚拟头结点。这个头结点上不存储数据，也就是 data字段为一个特殊的标识（例如 -1）。可以采用链表结点创建来生成一个虚拟头结点实例。

ListNode *head = ListCreateNode(-1);

二、链表的遍历

1
2
3
4
5
6
7
void ListTraversal(ListNode *head) {
    ListNode *tmp = head->next;
    while(tmp) {
        // 为所欲为
        tmp = tmp->next;
    }
}

ListTraversal代表对链表进行遍历。首先从头结点开始缓存到 tmp 中，继续循环访问 tmp的后继结点，直到链表的最后一个结点为止。在访问的过程中可以执行你需要的操作。

三、链表的调试

1、含义

调试就是通过一些可视化的方式最终将链表打印出来。一般利用遍历的方式实现。

2、源码

1
2
3
4
5
6
7
8
9
void ListPrint(ListNode *head) {
    ListNode *tmp = head->next;
    print("H -> ");
    while(tmp) {
        printf("%d -> ", tmp->data);
        tmp = tmp->next;
    }
    printf("NULL\n");
}

首先把虚拟头结点用 H表示并打印出来。然后遍历整个链表，遍历的过程中利用格式化打印出结点的值，再跟上一个 ->，最后在打印一个 NULL。这样一个链表就打印出来了

四、链表结点的索引

1、含义

链表结点的索引就是给定一个链表头和一个下标i，通过下标获取到链表的第 i 个元素。

2、源码

1
2
3
4
5
6
7
8
9
10
11
12
ListNode *ListGetNode(ListNode *head, int i) {	//(1)
    ListNode *tmp = head;
    int j = 0;									//(2)
    while(tmp && j < i) {						//(3)
        tmp = tmp->next;
        ++j;
    }
    if(!tmp) {									//(4)
        return NULL;
    }
    return tmp;									//(5)
}

（1）tmp 代表从链表头开始的 游标指针，用于对链表进行 遍历 操作。

（2）j 代表当前访问到了第 j 个结点。

（3）如果 游标指针 非空 并且 j < i，则代表还没访问到目标结点，继续执行循环，将 游标 的 后继结点 作为新一轮的 游标指针继续迭代。j 自增等价于将 j + 1 赋值给 j。

（4）当 游标指针 为空，则说明给定的i超过了链表长度，返回 空结点。

（5）最后返回找到的第 i 个结点。

五、链表结点的插入

1、含义

给定一个链表头和一个位置 i (i >= 0)和一个值 data，生成一个值为 data 的结点，并且将它插入到链表第 i 个结点之后的位置。

2、源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *ListInsertNode(ListNode *head, int i, DataType v) {
    ListNode *pre, *vtx, *aft;	//(1)
    int j = 0;	//(2)
    pre = head;
    while(pre && j < i) {		//(3)
        pre = pre->next;		//(4)
        ++j;
    }
    if(!pre) {					//(5)
        return NULL;
    }
    vtx = ListCreateNode(v);	//(6)
    aft = pre->next;
    vtx->next = aft;
    pre->next = vtx;
    return vtx;					//(7)
}

（1）预先定义三个指针，当结点插入完毕后 pre -> vtx -> aft。

（2）定义一个计数器，当 j == i 时表明找到要插入的位置。

（3）从 链表虚拟头结点 开始，迭代遍历链表，如果还没有到链表尾或者没有找到插入位置，则继续循环。

（4）将 游标指针 的 后继结点作为新一轮的 游标指针 继续迭代，计数器j自增 1。

（5）元素个数不足，无法找到给定位置 返回 NULL。

（6）创建一个值为v的 孤立结点，将vtx插入到pre -> aft之间，插入完毕后 pre -> vtx -> aft。

（7）最后返回插入的那个结点。

六、链表结点的删除

1、含义

给定一个链表头和一个位置 i (i >= 1)，将位置i的结点删除，并且返回被删除的结点。

（由于第 0 个结点是虚拟结点不能删除，所以 i 从 1 开始）

2、源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *ListDeleteNode(ListNode *head, int i) {
    ListNode *pre, *del, *aft;
    int j = 0;
    pre = head;					//(1)
    while(pre && j < i - 1) {	//(2)
        pre = pre->next;
        ++j;
    }
    if(!pre || !pre->next) {	//(3)
        return head;
    }
    del = pre->next;			//(4)
    aft = del->next;
    pre->next = aft;			//(5)
    free(del);					//(6)
    return head;
}

（1）第 0 个结点为虚拟头结点，规定不能删除，所以i从 1 开始

（2）从 链表头结点 开始遍历链表，找到将要被删除结点的 前驱结点 pre

（3）如果 前驱结点 为空，或者 需要删除的结点 为空，则直接返回当前 链表头结点

（4）缓存需要删除的结点到 del，缓存需要删除结点的 后继结点 到 aft

（5）将需要删除的结点的 前驱结点指向它的 后继结点，实现对目标节点的删除

（6）释放需要删除结点的内存空间，返回链表头结点

七、链表结点的查找

1、含义

即给定一个值，通过遍历链表找到链表值和给定值相等的那个结点。

2、源码

1
2
3
4
5
6
7
8
9
10
ListNode *ListFindNodeByValue(ListNode *head, DataType v) {
    ListNode *tmp = head;		//(1)
    while(tmp) {				//(2)
        if(tmp->data == v) {
        	return tmp;			//(3)
        }
        tmp = tmp->next;
    }
    return NULL;				//(4)
}

（1）从虚拟头结点开始遍历链表结点

（2）如果当前链表结点非空并且数据域不等于给定值，则继续访问它的后继结点，直到条件不成立

（3）返回最后访问到的那个结点

（4）未找到对应值，则返回空节点

八、链表结点的修改

1、含义

给定一个链表头、一个位置 i (i >= 1)和一个值 data，将位置i的结点值修改为 data，并且返回这个结点

2、源码

1
2
3
4
5
6
void LinkedListSet(head, i, data) {
    ListNode *tmp = ListGetNode(head, i);
    if (tmp) {
    	tmp->data = data;
    }
}

利用索引获取第 i 个链表结点，如果能够找到则将它的值赋值为 data

十、习题

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

206. 反转链表 - 力扣（LeetCode）

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

237. 删除链表中的节点 - 力扣（LeetCode）

24. 两两交换链表中的节点 - 力扣（LeetCode）

题解这种东西，看力扣上的大犇就好啦~