目录
1. 概念
链表是一种结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。也就是说链表的每一个节点，物理上不是连续存储的，每一个节点只有下一个结构体的地址信息。
相较于顺序表而言，每次新增一个节点只会新开辟一个节点的空间，而不是和顺序表一样，每次扩容需要翻倍增加新的空间。
2. 链表的实现
主要实现头插、头删、尾插、尾删。
注意：
①链表一般会设置一个头结点，这个头结点一般是一个结构体指针，那么要修改链表的时候（插入删除）需要传入这个指针的地址，也就是二级指针，才能修改链表的值。
②头插节点的时候，情况要考虑完全，头结点可能为空，头结点可能有值；当头结点为空的时候，直接将新节点作为头结点，当头结点不为空的时候需要将头结点的下一个节点保存起来（NULL或者其他节点），将头结点的next置为新节点，保存的节点作为新节点的next。
③尾删节点的时候，需要分三种情况，如果头结点为空，提示不能删除，如果只有头结点有值，那么头结点置空，如果至少有两个节点，那么需要找到倒数第二个节点（先找到最后一个，用一个变量每次保存当前遍历的节点），只需要释放倒数第一个节点，让倒数第二个节点的next指向空即可。
③查找节点的时候只需要传入头结点指针即可（结构体变量的地址），这里不传二级指针的原因是因为，没有涉及到修改链表的内容，这里如果找到了那个结构体，只需要返回当前结构体指针即可，后续根据这个结构体地址可以对这个结构体进行修改。
④这里删除、插入指定位置的后一个元素，并不是插入、删除当前元素，因为形参只有当前结构体地址，如果要删除当前的元素，需要再传一个头指针。
#define _CRT_SECURE_NO_WARNINGS
#include"single_list.h"
// 创建新节点
SingleListNode* createNode(dataType data)
{
SingleListNode* node = (SingleListNode*)malloc(sizeof(SingleListNode));
if (node == NULL)
{
printf("申请内存失败！");
exit(1);
}
node->data = data;
node->next = NULL;
return node;
}
// 尾插
void push_back(SingleListNode** head, dataType data)
{
SingleListNode* newNode = createNode(data);
if (*head == NULL)
{
*head = newNode;
}
else
{
SingleListNode* curr = *head;
while (curr->next != NULL) // 找到最后一个节点
{
curr = curr->next;
}
curr->next = newNode;
}
}
// 尾删
void pop_back(SingleListNode** head)
{
if (*head == NULL) // 1.链表为空
{
printf("空链表无法删除！");
exit(-1);
}
else if ((*head)->next ==NULL) // 2.链表只有一个元素
{
free(*head);
(*head) = NULL;
}
else
{
// 3.链表至少2个元素
// 遍历到倒数第二个
SingleListNode* curr = *head;
SingleListNode* prev = NULL;
while (curr->next != NULL)
{
prev = curr; // 倒数第二个节点
curr = curr->next;
}
free(curr);
prev->next = NULL;
}
}
// 头插
void push_front(SingleListNode** head, dataType data)
{
SingleListNode* node = createNode(data);
node->next = *head;
*head = node;
}
// 头删
void pop_front(SingleListNode** head)
{
if (*head == NULL)
{
printf("链表为空，不能删除");
exit(-1);
}
SingleListNode* tmp = *head;
*head = (*head)->next;
free(tmp);
}
// 遍历链表打印
void list_print(SingleListNode* head)
{
// 因为由头节点所以不需要判空
SingleListNode* curr = head;
while (curr != NULL)
{
printf("%d\n", curr->data);
curr = curr->next;
}
}
// 查找
SingleListNode* find(SingleListNode* head, dataType data)
{
if (head == NULL)
{
printf("链表为空，无法查找！");
exit(-1);
}
while (head)
{
if (head->data == data)
{
return head;
}
head = head->next;
}
return NULL;
}
// 插入指定位置的后面
void insert(SingleListNode** pos, dataType data)
{
assert(*pos);
SingleListNode* newNode = createNode(data);
newNode->next = (*pos)->next;
(*pos)->next = newNode;
}
// 删除指定位置的节点后面
void erase_pos(SingleListNode** pos)
{
assert(*pos);
SingleListNode* tmp = (*pos)->next;
(*pos)->next = tmp->next;
}3.相关OJ题
3.1删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度2，并且原数组 nums 的前两个元素被修改为1,2。不需要考虑数组中超出新长度后面的元素。
分析：
这里使用双指针法，左指针起始位置下标为0，右指针起始位置下标为1，判断右指针是否小于整个数组的长度。
当右指针所指向的数字等于左指针指向的数字，此时两个指针同时后移；
当右指针所指向的数字不等于左指针指向的数字，此时需要将左指针指向的数字存储到当前数组的第一个位置中（使用index作为下标）；此时两个指针同时后移。
这个数组的最后两个数，存在两种情况：
情况一：当这两个数不相等的时候，此时由于右指针最后+1，所以右指针会出右边界导致循环退出，最后一个数也是单独的数字，所以这里需要将最后一个数单独进行存储。
情况二：此时这两个数如果相同，那么在最后一次循环的时候已经保存过了，但是因为要保持程序的一致性，并且多赋一次值也不会对整个程序造成性能影响，所以这里的情况按照情况一来处理。
代码：
int removeDuplicates(int* nums, int numsSize) {
int left = 0;
int right = 1;
int index = 0;
// 循环条件写在循环体中
for(right;right < numsSize;)
{
// 左右指针值相同，左右指针移动
if(nums[left] == nums[right])
{
}else
{
// 左右指针值不相同，左指针赋值给index下标处
nums[index++] = nums[left];
}
left++;
right++;
}
// 最后一个元素若不同，需要再次赋值，相同则赋值没影响
nums[index] = nums[left];
index++;// 最后新数组的下标就是元素的个数
return index;
}3.2 数组形式的整数加法
整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。
- 例如，对于
num = 1321，数组形式是[1,3,2,1]。
给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
示例 1：
输入：num = [1,2,0,0], k = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234
分析：
这道题目的细节非常多，虽然标注的是简单题，但是可能对于初学者来说是中等题。总体思路一定不能直接把数组的数字转换成整型，如果数组的长度>30，那么整型就会溢出，所以这里其实在考大数相加的问题。
我们可以将数组的每一位数字和k的每一位数字进行相加，一共要加多少次呢？3位数+2位数只需要加3次，也就是说循环的次数是位数更多的数字的位数。
那么我们可以将相加的结果存在一个数组中，那么数组的长度怎么算呢？刚刚我们已经计算出来了两数较长的以为数的位数，只需要在此位数+1就是我们开辟数组的长度了，最极端的情况，三位数+三位数在进位的情况下，是四位数。流程梳理清楚，开始写代码。
①计算出k的位数为k_size；
②计算出k_size和num_size较大值，len；
③开辟出len+1的数组空间；
④开始按位相加，总共循环len次；
⑤当数组中的数字位数 < k的位数的时候，数组会越界，所以这里需要判断数组的合法下标，如果数组下标合法那就将该位参与运算，若不合法则使用0参与运算；
⑥k的末位和数组的最后一位数字（合法）相加，这里记录变量nextNum，表示是否进位，如果和>9那么说明需要进位，nextNum标注为1，否则是0，下一次按位相加的时候+nextNum,；
⑦此时和记录为ret，将ret的个位数存在返回数组的第一位、第二位以此类推；
⑧循环结束之后，需要判断两个数的第一位相加之后，是否需要进位，例如215 + 806 = 1021；
由于循环只进行了三次，所以进位的数字没有进行保存，这里判断如果进位位1，那么需要单独处理，将1赋给返回数组的最新位，此时记录返回数组的下标再+1；
⑨将数组逆置，返回返回数组，此时的下标就是该数组的长度。
代码：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
/*
1.判断两个数哪个位数更长，创建新数组的长度就是改位数+1；
2.从末尾开始按位相加，一共加的次数是长的那个数字的位数；
3.相加完毕之后，是否进位需要进行保存，计算完毕的数字需要存放在新数组的首元素位置；
4.循环开始的时候需要增加进位；
5.如果数组的位数更大，那么需要判断合法性；
6.将最后的数组逆序就是最后的结果。
*/
int k_num = k;
// 1.判断数字的长度
int k_size = 0;
while (k) {
k /= 10;
k_size++;
}
int len = k_size > numSize ? k_size : numSize;
int* retArr =
(int*)malloc(sizeof(int) * (len + 1)); // 三位数+三位数 = 四位数
// 2.按位计算
int num_i = numSize - 1;
int nextNum = 0; // 是否需要进位
int ret_i = 0;
while (len--) {
// 当数组长度小于数字长度，那么此时len是数字长度就会越界
// 判断数组下标是否合法
int legal_num = 0;
if(num_i >= 0)
{
legal_num = num[num_i];
num_i--;
}
int ret = legal_num + k_num % 10 + nextNum;
if (ret > 9) {
nextNum = 1;
} else {
nextNum = 0;
}
k_num /= 10;
// 给新数组赋值
retArr[ret_i++] = ret % 10;
}
// 如果nextNum == 1说明，第一位相加的时候需要进位，但是还没有处理
if(nextNum == 1)
{
retArr[ret_i] = 1;
ret_i++;
}
// 将数组逆序
int left = 0;
int right = ret_i - 1;
while(left < right)
{
int tmp = retArr[left];
retArr[left] = retArr[right];
retArr[right] = tmp;
left++;
right--;
}
*returnSize = ret_i;
return retArr;
}3.3 反转单链表（非递归）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
分析1：
①需要准备三个指针，第一个指针指向空，二、三指针分别指向head和head的next；
②这里需要先判断链表元素为1或者0的情况，这里直接返回head本身即可；
③2个或者2个以上的元素：第二个指针指向第一个指针、第一个指针重新赋值为第二个指针，第二个指针重新赋值为第三个指针、第三个指针重新赋值为他的下一个指针。
所以每次逆向的操作都由n1和n2来完成，n3需要每次向后即可，给n2提供保证。
④循环条件是当第三个指针为空就停止，循环停止的时候，第二个指针还没来得及指向第一个指针循环就结束了，这时候需要手动进行指向。
代码1:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
// 三指针
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
if(head ==NULL || head->next == NULL)
{
return head;
}
struct ListNode* n3 = head->next;// 保存第三个变量
while(n3)
{
n2->next = n1;
n1 = n2;
n2 = n3;
n3 = n3->next;
}
// 此时n3为空，但是n2没有指向n1
n2->next = n1;
return n2;
}分析2：
使用一个新链表，遍历老链表，每次遍历一个元素对新链表进行头插，需要注意的是需要将当前指针的下一个元素进行保存，不然无法迭代。
代码2：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* newhead = NULL;
struct ListNode* curr = head;
// 遍历原链表，将元素头插到新链表中
while (curr) {
struct ListNode* nt = curr->next;
curr->next = newhead;
newhead = curr;
curr = nt;
}
return newhead;
}