【数据结构】链表

引言：

什么是链表？？

简单来说，链表就是通过指针串联起来的线性结构，每个节点由两部分构成，值域与指针域。指针域内存放的是下一个节点的内存地址。

链表的储存方式

大家都知道，数组在内存中的空间是连续的。但是链表不是，链表通过，每个指针的指针域，链接每个节点在内存中的位置。

链表的种类

单链表

以上说的就是单链表！

双链表

单链表中，每个节点只存放一个数据域与一个指针域(内部存放下一个节点的位置)。

而双链表中，每一个节点存放一个数据域与两个指针域，一个指针域存放的是上一个节点的地址，另一个指针域存放的是下一个节点的地址，这样，就能同时向两侧进行查询。

循环链表

简单解释就是，单链表形成了环。

链表的定义

单链表的定义

struct ListNode{int val;ListNode* next;ListNode():val(0),next(nullptr){};ListNode(int x):val(x),next(nullptr){};
};

初始化

ListNode* cur1 = new ListNode(2);
ListNode* cur2 = new ListNode();
cur2->val = 2; // (*cur2).val = 2;

双链表的定义

// 定义双向链表节点结构体
struct ListNode {int val;ListNode* prev;  // 指向前一个节点的指针ListNode* next;  // 指向后一个节点的指针ListNode() : val(0), prev(nullptr), next(nullptr) {}ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

C++中，是如何运用该链表的！！！

其实这才是重点！哈哈STL库！我最喜欢用了！接下来，就好好的说一下stl！

<list>是C++标准模板库中的一个序列容器。可以不用向<vector>一样，在创建时指定大小。

优点是删除、插入为O(1)，缺点是查找速度是O(N)

以下是简单的增删改查的运用。

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
int main(){list<int> l;// 增l.push_back(2);l.push_front(1);// 查for(int i:l) cout<<i;cout<<endl;for(auto it= l.begin(); it!=l.end(); ++it) cout<<*it<<endl;// 改 - 遍历的时候修改// 删// 结合这迭代器删auto it = find(l.begin(),l.end(),3);if(it!=l.end()) l.erase(it); // 必须要判断一下for(auto it= l.begin(); it!=l.end(); ++it) {if(*it==3)l.erase(it); // 当然也能这样删除一下}// 引入remove删，直接删除所有l.remove(3);// 头删、尾删l.pop_front();l.pop_back();return 0;
}

好吧，当我写完之后，发现我又不是那么喜欢它了！(┬┬﹏┬┬)，好像也不是那么好用。相比于<vector>。

大纲

1、移除链表元素-（解析）-设置一个头节点

2、 设计链表-（解析）-基操

3、反转链表-（解析）-临时节点的优雅运用

4、两两交换链表中的节点-（解析）-优雅运用临时节点

5、删除链表的倒数第 N 个结点-（解析）-双指针用法

6、链表相交-（解析）-数学思维，列公式

7、环形链表 II-（解析）-数学思维，Floyed判圈(龟兔赛跑)，初步洞悉算法

8、左移右移 -（解析）-蓝桥真题，运用struct与数组，跳出链条问题

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！

题目

​​​​​​一、移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

​

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
// 设置一个虚拟节点，可以事半功倍
public:ListNode* removeElements(ListNode* head, int val) {// 整理一个虚拟头节点ListNode* curHead = new ListNode(-1);curHead->next = head;ListNode* cur = curHead;while(cur->next!=nullptr){if(cur->next->val==val) cur->next=cur->next->next;else cur=cur->next;} return curHead->next;}
};

二、 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

• 0 <= index, val <= 1000
• 请不要使用内置的 LinkedList 库。
• 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

class MyLinkedList { // 创建一个链表，真为链表
public:struct LinkedList{ // 创建节点int val;LinkedList* next;LinkedList():val(0),next(nullptr){}LinkedList(int x): val(x),next(nullptr){}LinkedList(int x,LinkedList* next): val(x),next(next){}};MyLinkedList() { // 初始化用的_dummyHead = new LinkedList(0); // 首元节点size = 0;}int get(int index) {if(index>=size){return -1;}LinkedList* _dummyCur = _dummyHead;while(index--){_dummyCur = _dummyCur->next;}return _dummyCur->next->val;}void addAtHead(int val) {LinkedList* cur = new LinkedList(val); // 创建临时节点cur->next = _dummyHead->next;_dummyHead->next = cur;size++;}void addAtTail(int val) {LinkedList* cur = new LinkedList(val); // 创建临时节点LinkedList* _dummyCur = _dummyHead;while(_dummyCur->next != nullptr){_dummyCur=_dummyCur->next;}_dummyCur->next = cur;size++;}void addAtIndex(int index, int val) {if(index>=size){ // 如果，长度与index相等的情况下if(index==size) addAtTail(val);return;}LinkedList* cur = new LinkedList(val); // 创建临时节点LinkedList* _dummyCur = _dummyHead;while(index--){ // 换位置_dummyCur=_dummyCur->next;}// 插cur->next = _dummyCur->next;_dummyCur->next = cur;size++;}void deleteAtIndex(int index) {if(index>=size) return;  // 无效LinkedList* _dummyCur = _dummyHead;while(index--){_dummyCur=_dummyCur->next;}_dummyCur->next= _dummyCur->next->next; // 直接跳过size--;}
private: // 创建本函数中，宏观上需要的东西int size;LinkedList* _dummyHead;
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

三、反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

​

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

​

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
// 其实就是临时节点的运用
public:ListNode* reverseList(ListNode* head) { // 其实挺简单的，但是为啥我就想这么久呢ListNode* cur = head;ListNode* temp1 = nullptr;ListNode* temp2 = nullptr;while(cur!=nullptr){temp1 = cur->next;cur->next = temp2;temp2 = cur;cur = temp1;}return temp2;}
};

四、两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

​

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) { // 建立几个临时变量存储// 这两步，是基操ListNode* dummyCur = new ListNode(0);dummyCur->next = head;ListNode* cur = dummyCur;ListNode* temp1 = nullptr;ListNode* temp2 = nullptr;while(cur->next!=nullptr&&cur->next->next!=nullptr){temp1 = cur->next;temp2 = cur->next->next;temp1->next = temp2->next;temp2->next = temp1;cur->next = temp2;cur = temp1;}return dummyCur->next;}
};

五、删除链表的倒数第 N 个结点

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

示例 1：

​

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
// 简单运用双指针法
public:ListNode* removeNthFromEnd(ListNode* head, int n) { // 要想一趟实现，双指针法ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;ListNode* left = dummyHead;n  = n+1;while(n--) cur = cur->next;while(cur!=nullptr){left = left->next;cur = cur->next;}left->next = left->next->next;return dummyHead->next;   }
};

六、链表相交

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

图示两个链表在节点 c1 开始相交：

​

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

​

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

​

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

​

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/// 这压根就是一道数学题，一道数学思想// 还有指针变换时，地址会改变的细节(┬┬﹏┬┬)/*大概意思就是，一个指针走了 a+c+b的长度另一个指针，走了 b+c+a 的长度最后一定会相交*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 其实这个应该也挺好写的ListNode* a = headA; ListNode* b = headB;while(headA!=headB){ // a与b一直在改变headA = headA!=nullptr ? headA->next : b;headB = headB!=nullptr ? headB->next : a;}return headA; }
};

七、环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

​

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

​

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

​

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {// 涉及数学思想，数学的推理过程-->Floyd 判圈算法（也称为龟兔赛跑算法）,如果搜的化，直接问数学思想// 当然，本题也能用哈希方式解决
public:ListNode *detectCycle(ListNode *head) {// 涉及快慢指针ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr&&fast->next!=nullptr){fast = fast->next->next;slow = slow->next;if(fast==slow) break;}if(fast==nullptr||fast->next==nullptr) return nullptr;ListNode* ptr = head;while(ptr!=slow){ptr=ptr->next;slow=slow->next;}return ptr;}
};

八、

1. 左移右移

问题描述

小蓝有一个长度为 NN 的数组, 初始时从左到右依次是 1,2,3,…N1,2,3,…N 。

之后小蓝对这个数组进行了 MM 次操作, 每次操作可能是以下 2 种之一:

1. 左移 xx, 即把 xx 移动到最左边。

2. 右移 xx, 即把 xx 移动到最右边。

请你回答经过 MM 次操作之后, 数组从左到右每个数是多少?

输入格式

第一行包含 2 个整数, NN 和 MM 。

以下 MM 行每行一个操作, 其中 “L xx "表示左移 x,"Rxx,"Rx "表示右移 xx 。

输出格式

输出 NN 个数, 代表操作后的数组。

样例输入

样例输出

2 3 4 5 1

样例说明

样例中的数组变化如下:

[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1][1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定

对于 50%50% 的评测用例, 1≤N,M≤100001≤N,M≤10000.

对于 100%100% 的评测用例, 1≤N,M≤200000,1≤x≤N1≤N,M≤200000,1≤x≤N.

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {// 涉及数学思想，数学的推理过程-->Floyd 判圈算法（也称为龟兔赛跑算法）,如果搜的化，直接问数学思想// 当然，本题也能用哈希方式解决
public:ListNode *detectCycle(ListNode *head) {// 涉及快慢指针ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr&&fast->next!=nullptr){fast = fast->next->next;slow = slow->next;if(fast==slow) break;}if(fast==nullptr||fast->next==nullptr) return nullptr;ListNode* ptr = head;while(ptr!=slow){ptr=ptr->next;slow=slow->next;}return ptr;}
};

八、左移右移

问题描述

小蓝有一个长度为 NN 的数组, 初始时从左到右依次是 1,2,3,…N1,2,3,…N 。

之后小蓝对这个数组进行了 MM 次操作, 每次操作可能是以下 2 种之一:

1. 左移 xx, 即把 xx 移动到最左边。

2. 右移 xx, 即把 xx 移动到最右边。

请你回答经过 MM 次操作之后, 数组从左到右每个数是多少?

输入格式

第一行包含 2 个整数, NN 和 MM 。

以下 MM 行每行一个操作, 其中 “L xx "表示左移 x,"Rxx,"Rx "表示右移 xx 。

输出格式

输出 NN 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明

样例中的数组变化如下:

[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1][1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定

对于 50%50% 的评测用例, 1≤N,M≤100001≤N,M≤10000.

对于 100%100% 的评测用例, 1≤N,M≤200000,1≤x≤N1≤N,M≤200000,1≤x≤N.

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

 Java版

import java.util.Scanner;public class ArrayManipulation {public static void main(String[] args) {// 创建 Scanner 对象用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 读取数组的长度 n 和操作的次数 mint n = scanner.nextInt();int m = scanner.nextInt();// 定义操作结构体数组，这里用两个数组来模拟结构体的功能// 一个数组存储操作的方向（字符 'L' 或 'R'）char[] directions = new char[m];// 一个数组存储操作对应的数字int[] numbers = new int[m];// 读取 m 次操作，将操作方向和对应的数字分别存储到相应数组中for (int i = 0; i < m; i++) {directions[i] = scanner.next().charAt(0);numbers[i] = scanner.nextInt();}// 标记数组，用于标记某个数字是否已经被处理过boolean[] flag = new boolean[n + 1];// 结果数组，用于存储最终操作后的数组元素int[] res = new int[n];// 左指针，用于从结果数组的左边开始填充元素int st = 0;// 右指针，用于从结果数组的右边开始填充元素int en = n - 1;// 逆向遍历操作数组，这样可以确保最后一次操作的元素优先被处理// 因为最后一次操作对元素位置的影响是最终有效的for (int i = m - 1; i >= 0; i--) {int num = numbers[i];// 如果该数字已经被处理过，跳过本次操作if (flag[num]) {continue;}// 如果操作方向是 'L'，表示左移操作if (directions[i] == 'L') {// 将该数字放到结果数组的左边，然后左指针右移一位res[st++] = num;} else {// 如果操作方向是 'R'，表示右移操作// 将该数字放到结果数组的右边，然后右指针左移一位res[en--] = num;}// 标记该数字已经被处理过flag[num] = true;}// 遍历从 1 到 n 的所有数字，将未被操作过的数字按顺序添加到结果数组中for (int i = 1; i <= n; i++) {if (!flag[i]) {res[st++] = i;}}// 输出结果数组，元素之间用空格分隔，最后一个元素后面不跟空格for (int i = 0; i < n - 1; i++) {System.out.print(res[i] + " ");}System.out.print(res[n - 1]);// 关闭 Scanner 对象，释放资源scanner.close();}
}

C++版：

#include <iostream>
using namespace std;
// 且看，本题是如何绕开权重，思考问题的(┬┬﹏┬┬)，受教了
// 将每一步操作，存起来，后续满满释放的
const int N = 1e6+5;
// 全局变量自带初始化
struct Op{char c;int num;
}op[N];
bool flag[N]; // 表示是否标记过
int res[N]; // 存放结果
int main(){int n,m;cin>>n>>m;for(int i=0; i<m; ++i){ // 存放cin>>op[i].c>>op[i].num;}int st=0,en=n-1;for(int i=m-1; i>=0; --i){ // 逆向思维，破解权重问题if(flag[op[i].num]) continue;if(op[i].c=='L') res[st++]=op[i].num;else res[en--]=op[i].num;flag[op[i].num] = true; // 表示已经遍历过}for(int i=1; i<=n; ++i){if(!flag[i]) res[st++]=i;}for(int i=0; i<n-1; ++i){cout<<res[i]<<" ";}cout<<res[n-1];return 0;
}

知识点

一、什么是算法 :: 基础认知 ::

• 算法是一组明确的指令，用于完成任务，无论是否涉及数学。（如食谱、整理文件）
• 算法的核心并不依赖于数学，而是基于明确的步骤与逻辑去解决问题，这才是关键。
• 数学更多的只是起到优化算法的作用。

借鉴博客：

1、什么是链表？（图解）

2、【数据结构】链表(单链表实现+详解+原码)

3、链表理论基础

4、C++ 容器类 <list>

5、什么是算法

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！