【数据结构入门】链表

目录

1. 概念

2. 链表的实现

3.相关OJ题

3.1删除有序数组中的重复项

分析：

代码：

 3.2 数组形式的整数加法

分析：

代码：

3.3 反转单链表（非递归）

分析1：

代码1:

分析2：

代码2：

---

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没有指向n1n2->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;
}