代码随想录之链表刷题总结

目录

1.链表理论基础

2.移除链表元素

3.设计链表

4.翻转链表

5.两两交换链表中的节点

6.删除链表中的第N个节点

7.链表相交

8.环形链表

---

1.链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

如下图所示：

链表的类型

单链表

也就是刚才所说的

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示：

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中是连续分布的，但是**链表在内存中不是连续分布**的。

链表是**通过指针域的指针链接在内存中各个节点**。

所以链表中的节点在内存中不是连续分布的 ，而是**散乱分布在内存中的某地址上**，分配机制取决于操作系统的内存管理。

如图所示：

这个链表起始节点为2， 终止节点为7，  各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的定义

C/C++的定义链表节点方式，如下所示：

struct ListNode {int val;//存储节点上面的元素值ListNode* next;//用于指向链表的下一个节点，初始时被设置wULL，表示当前节点是链表的末尾ListNode(int x) : val(x),next(NULL) {}//构造函数，初始化ListNode的实例，接收一个整型参数x，并将这个值赋给当前节点的val成员，//同时将next指针初始化为NULL，表示这个节点后面没有更多的节点};
/*操作示例*/
ListNode* head = new ListNode(1);//创建链表的头节点，值为1
head->next = new ListNode(2);//在头节点后面添加一个新的节点，值为2

有同学说了，我不定义构造函数行不行，答案是可以的，C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

链表的操作

删除节点

删除D节点，如图所示：

只要将C节点的next指针 指向E节点就可以了。

那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。

是这样的，所以在C++里最好是再手动释放这个D节点，释放这块内存。

其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

添加节点

如图所示：

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

把链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

2.移除链表元素

题目：

题意：删除链表中等于给定值 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 输出：[]

思路：

先设置虚拟头节点，因为第一个节点也有可能是val值，然后移除的操作其实就是val值的前一个节点直接跳过val节点，指向val的下一个节点

注意：跳过的节点记得手动释放一下内存，节省空间

代码如下：

class Solution {
public:ListNode* removeElement(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while (cur->val != NULL) {if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;}
};

3.设计链表

题目

a.get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回 - 1。
b.addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
c.addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
d.addAtIndex(index, val)：在链表中的第 index 个节点之前添加值为 val  的节点。
如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
e.deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

注意：

注意初始定义链表的状态

自己在纸上面写一遍

注意index的区间边界，搞清楚链表中的移动大小，以便在正确的位置做插入删除操作

代码如下：

class MyLinkedList {
public:struct ListNode {int val;ListNode* next;ListNode(int val) :val(val), next(nullptr) {}};// 初始化链表MyLinkedList() {_dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点_size = 0;}//a.get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回 - 1。int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}else {ListNode* cur = _dummyHead->next;while (index--) {cur = cur->next;}return cur->next->val;}}//b.addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}//c.addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。void addAtTail(int val) {ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while (cur->next != NULL) {cur = cur->next;}newNode->next = cur;}
//d.addAtIndex(index, val)：在链表中的第 index 个节点之前添加值为 val  的节点。
//如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。void addAtIndex(int index, int val) {if (index > _size) return;if (index < 0) index = 0;ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}//e.deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。void deleteAtIndex(int index) {ListNode* cur = _dummyHead;if (index > _size - 1 || index < 0) {return;}while (index--) {cur = cur->next;}ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;temp = NULL;_size--;}//打印链表void printLinkedList() {ListNode* cur = _dummyHead;while (cur->next != NULL) {cout << "cur->next-val = " << cur->next->val << endl;cur = cur->next;}cout << endl;}
public:ListNode* _dummyHead;int _size;
};

4.翻转链表

题目：

题意：反转一个单链表(是将箭头翻转，不是里面的元素进行翻转)。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路：

设置双指针法，一个pre先指向NULL，然后cur在head节点，不断更新指向

注意：

使用temp先保存cur->next，因为指向改变了，不存储的话无法继续进行

代码如下：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = NULL;ListNode* cur = head;ListNode* temp = new ListNode(0);while (cur) {temp = cur->next;cur->next = pre;//更新pre和curpre = cur;cur = temp;}return pre;}
};

5.两两交换链表中的节点

题目：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：

按照下图中的三部进行操作即可

注意：

记得保存cur->next与cur->next->next->next的值，因为指向发生了改变

代码：

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while (cur->next != nullptr && cur->next->next != nullptr) {ListNode* temp = cur->next;ListNode* temp1 = cur->next->next->next;/*dummyhead->next = temp1;temp1->next = temp;temp = cur->next->next->next;*///错误写法，不可取cur->next = cur->next->next;cur->next->next = temp;cur->next->next->next = temp1;cur = cur->next->next;}ListNode* result = dummyhead->next;delete dummyhead;return result;}
};

6.删除链表中的第N个节点

题目：

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

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

示例 2：

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

示例 3：

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

思路：

使用双指针法进行解决，先定义fast指针和slow指针，初始化为虚拟头节点，fast先走n步，然后俩指针一起开始移动，直到fast变为NULL停止，此时slow指向的正好是删除节点的前一个节点，这是再改变节点指向即可

注意：

slow一定要在删除节点的前一个，不然无法继续操作

对于while循环中的逻辑要充足考虑，不要漏掉情况

代码如下：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* slow = dummyhead;ListNode* fast = dummyhead;while (n--&&fast->next!=nullptr) {fast = fast->next;}while (fast->next != nullptr) {slow = slow->next;fast = fast->next;}slow->next = slow->next->next;return dummyhead->next;}
};

7.链表相交

题目：

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

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

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

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

思路：

此时一定要充分理解链表相交，：若两个链表相交，则两个链表有共同的节点，从这个节点之后，后面的节点都会重叠，直到链表结束，若相交，则两个链表呈现Y字型

 先计算两个列表的长度差值，让curA和curB这两个指针对齐，然后再移动，判断指针是否相等

如下图：

注意：

明确链表相交是什么

判断的是指针，不是数值

代码：

class Solution {ListNode* listjiao(ListNode* headA, ListNode* headB) {ListNode* curA = headA;ListNode* curB = headB;int sizeA = 0;int sizeB = 0;while (curA != nullptr) {sizeA += 1;curA = curA->next;}while (curB != nullptr) {sizeB += 1;curB = curB->next;}if (sizeB > sizeA) {swap(sizeA, sizeB);swap(headA, headB);}int gap = sizeA - sizeB;while (gap--) {curA = curA->next;}while (curA != nullptr) {if (curA == curB) {return curA;}else {curA = curA->next;curB = curB->next;}}return NULL;}
};

8.环形链表

题目：

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思路：

判断1：链表是否有环
快慢指针法，从头节点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，若相遇就是有环。
判断2：环的入口节点
分别从头节点以及相遇节点出发一个指针，每次只走一个，相遇的时候就是入口节点

注意：

最后返回的是环形入口节点

代码：

class Solution {
public:ListNode* detecCycle(ListNode* head) {ListNode* fast = head;ListNode* slow = head;//while (fast->next->next != nullptr && slow != nullptr) {//啰嗦了，可以改一下while(fast!=NULL&&fast->next!=NULL) {fast = fast->next->next;slow = slow->next;//快慢指针相遇if (fast == slow) {ListNode* index1 = head;ListNode* index2 = fast;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index1;}}return nullptr;}
};