【数据结构】链表_数据结构链表的博客

引言：

什么是链表？？

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

链表的储存方式

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

​

链表的种类

单链表

以上说的就是单链表！

双链表

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

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

​

循环链表

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

​

链表的定义

单链表的定义

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！

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

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

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

#include #include #include using namespace std;int main(){ list 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;}

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

大纲

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->3myLinkedList.get(1);  // 返回 2myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3myLinkedList.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 3L 3L 2R 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 和操作的次数 m int 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 = 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 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>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++ 容器类

5、什么是算法

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