1. 链表理论基础
代码随想录 原文
- 链表是一种通过指针串联在一起的线性结构
- 节点由数据域和指针域组成，指针域存放指向下一个节点的指针
- 链表的入口节点称为链表的头结点
1.1 链表类型
单链表
- 单链表中的指针域只能指向节点的下一个节点
- 最后一个节点的指针域指向null
双链表
- 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点
- 既可以向前查询也可以向后查询
循环链表
- 链表首尾相连，一个节点的指针域指向链表的头结点
1.2 链表存储
- 链表在内存中不是连续分布的
- 链表是通过指针域的指针链接在内存中各个节点
- 链表散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理
1.3 链表定义
面试需要手写链表
C/C++的定义链表节点方式：
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
C++也可以使用默认构造函数初始化节点，但初始化的时候就不能直接给变量赋值。
//通过自己定义构造函数初始化节点
ListNode* head = new ListNode(5);
//使用默认构造函数初始化节点：
ListNode* head = new ListNode();
head->val = 5;
1.4 链表操作
删除节点
删除D节点：
- 将C节点的next指针 指向E节点
- 在C++里最好是再手动释放这个D节点的内存
添加节点
- 将C节点的next指针 指向F节点
- 将F节点的next指针 指向D节点
1.5 性能分析
| 插入/删除(时间复杂度) | 查询(时间复杂度) | 适用场景 | |
|---|---|---|---|
| 数组 | 数据量固定，较少增删，频繁查询的场景 | ||
| 链表 | 数据量固定，频繁增删，较少查询的场景 |
2. 移除链表元素
代码随想录 原文
力扣题目： 203.移除链表元素
2.1 思路
删除的不是头节点：
就是让节点next指针直接指向下下一个节点就可以了
从内存中删除这移除的节点
删除的是头节点：
- 直接使用原来的链表来进行删除操作
将头结点向后移动一位，就从链表中移除了一个头结点。
- 设置一个虚拟头结点在进行删除操作
- 可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
- return 头结点的时候，需要返回新的头结点
return dummyNode->next;
2.2 代码
直接使用原来的链表来进行移除节点操作：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next!= NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
设置一个虚拟头结点在进行移除节点操作：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while (cur->next != 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. 链表功能实现
代码随想录 原文
力扣题目： 707.设计链表
3.1 思路
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
设置一个虚拟头结点在进行操作（操作一致！）
3.2 代码
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
// 初始化链表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
_size = 0;
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){ // 如果--index 就会陷入死循环
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
void addAtIndex(int index, int val) {
if(index > _size) return;
if(index < 0) index = 0;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
void deleteAtIndex(int index) {
if (index >= _size || index < 0) {
return;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
// 打印链表
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
LinkedNode* _dummyHead;
};
4. 反转链表
代码随想录 原文
力扣题目： 707.设计链表
面试常考
4.1 思路
定义一个新的链表，实现链表元素的反转（浪费内存空间）
- 在原始链表操作
- 改变链表的next指针的指向，直接将链表反转
双指针法：
- 定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null
- cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
- 将cur->next 指向pre ，此时已经反转了第一个节点了
- 循环移动pre和cur指针
- cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点
递归法：
1. 和双指针法是一样的逻辑，从前往后翻转指针指向
反转函数（cur ，pre）{
判断（cur是否为空，是否结束）
是：return pre
否：cur->next 指向pre
循环移动pre和cur指针
再调用：反转函数（cur ，pre）
}
先了解双指针法再学习递归
2. 不同思路的递归写法，从后往前翻转指针指向
4.2 代码实现
双指针法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
递归法从前往后翻转指针指向
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
递归法从后往前翻转指针指向
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 边缘条件判断
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 递归调用，翻转第二个节点开始往后的链表
ListNode *last = reverseList(head->next);
// 翻转头节点与第二个节点的指向
head->next->next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head->next = NULL;
return last;
}
};
5 .总结
- 链表的定义要能手撕
- C，C++编程语言的话，移除链表元素还需要从内存中删除这两个移除的节点
- 设置一个虚拟头结点，原链表的所有节点就都可以按照统一的方式进行操作
- 反转链表要先了解双指针法，再了解递归法
- 返回链表的头节点要确认是否返回正确
学习时间180min
评论区