链表的概念以及结构
概念：链表是一种物理存储结构上不连续的、非顺序的存储结构，数据元素的顺序是通过节点中的指针来实现的。
结构：（此处指单向非循环链表）链表中每个节点的存储元素一般包含两部分，数据和下一个节点的地址。
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
![链表结构示意图]
遍历打印链表
在链表中访问元素需要通过每个节点中存放的下一个元素地址，才能找到下一个节点的位置。具体代码实现如下：
// 遍历链表
void SListPrint(SListNode* phead) {
SListNode* cur = phead; // 创建一个指针来指向头结点的位置
while(cur) {
printf("%d->", cur->val); // 打印当前节点的数据
cur = cur->next; // 将指针指向下一个节点
}
}
申请节点
链表中每一个节点都是动态开辟出来的，所以要新增一个节点之前要先申请一个节点，每个节点的大小为该结构体的大小，开辟成功之后，该节点数据部分存放输入的值，地址（next）置为 NULL。
C 语言代码展示如下（这部分主要是为了了解具体实现步骤）：
// 申请节点
SListNode* SListBuyNode(SListNodeDataType x) {
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 申请地址空间
if (newnode == NULL) { // 判断是否成功
perror("malloc:");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
用 C++ 则更为简洁且更加安全，代码如下：
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {};
};
ListNode* newNode = new ListNode(newValue);
尾插
因为链表无法通过元素下标访问，所以我们要想知道下一个节点的位置，只能通过遍历整个链表。
这里分为两种情况：
- 链表为空，直接插入
- 链表不为空，遍历找到尾节点，再插入
// 尾插
void SListPushBack(ListNode** head, int x) {
ListNode* newNode = new ListNode(x); // 创建一个新节点
if(head == nullptr) {
*head = newNode; // 如果要插入的链表为空，则直接将新建的节点作为头节点即可
} else {
ListNode* current = *head;
while(current != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
头插
在头部插入的话，只需要将当前节点置为头节点，再将当前节点的 next 改为头节点。
// 头插
void SListPushFront(ListNode** head, int x) {
// 申请新增节点
ListNode* newNode = new ListNode(x);
// 将当前节点的 next 改为头节点
newNode->next = *head;
// 将头节点设为当前节点
*head = newNode;
}
函数参数 ListNode* head 是值传递，这意味着函数内部对 head 的修改不会影响到函数外部的实参。如果要修改外部的头指针，应该传递头指针的指针（ListNode** head）或者头指针的引用（ListNode*& head）。
删除
- 链表为空，不能删除
- 删除头节点：如果要删除的是头节点，先保存头节点，再将下一个节点更新为头节点
- 删除其余位置节点
具体代码展示如下：
// 删除链表中值为 target 的节点
ListNode* deleteNode(ListNode* head, int target) {
// 链表为空
if(head == nullptr) {
return nullptr;
}
// 删除头节点
if(head->val == target) {
// 先记下头节点位置
ListNode* temp = head;
head = head->next;
delete temp;
return head;
}
// 删除其余位置
ListNode* cur = head;
// 找到目标位置的前一个节点
while(cur->next && cur->next->val != target) {
cur = cur->next;
}
if(cur->next) {
ListNode* temp = cur->next; // 记录下要删除节点的下一个节点
cur->next = cur->next->next; // 跳过要删除的节点
delete temp; // 删除节点
}
return head;
}
最后再加一个判断 if(cur->next !=nullptr) 的原因：
目标节点不存在于链表中：如果链表中不存在值为 target 的节点，while 循环会一直执行到链表末尾，此时 cur->next 为 nullptr。当 while 循环条件 cur->next != nullptr && cur->next->val != target 中的 cur->next == nullptr 时，循环终止。在这种情况下，就不应该执行删除操作，因为没有找到要删除的节点。所以 if (cur->next != nullptr) 这个判断可以防止在链表中没有目标节点时误删节点或引发空指针异常。
nullptr 和 NULL 的区别
在 C++ 中，nullptr 和 NULL 都用于表示空指针，但它们之间存在一些重要区别：
- nullptr：
nullptr是 C++ 11 引入的关键字，它的类型是std::nullptr_t。这是一种特殊的类型，专门用于表示空指针。它可以隐式转换为任何指针类型，使得代码在处理空指针时更加类型安全。例如：
int* ptr1 = nullptr;
double* ptr2 = nullptr;
- NULL：
NULL是一个宏，通常在 C 标准库头文件（如<stdio.h>）或 C++ 兼容头文件中定义。在 C 语言中，它通常被定义为((void*)0)，在 C++ 中，它通常被定义为0或0L（长整型 0）。由于它本质上是整数类型（在 C++ 中），当将NULL赋值给指针时，可能会导致一些潜在的类型混淆问题。例如，假设有一个函数重载，同时接受指针和整数类型参数：
void func(int num);
void func(int* ptr);
func(NULL); // 在 C++ 中，这可能会导致编译错误或调用错误的函数，因为 NULL 可能被解释为整数 0
func(nullptr); // 明确调用 func(int* ptr)
经典算法题示例
题目一：反转链表
![反转链表示意图]
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode 类
* @return ListNode 类
*/
ListNode* ReverseList(ListNode* head) {
ListNode* per = nullptr; // 定义前序节点
while(head) { // 判断是否到结尾
ListNode* temp = head->next; // 记录下一个节点
head->next = per; // 反转当前节点
per = head; // 前序节点向后移
head = temp; // 当前节点后移
}
return per;
}
};
总结：逐个翻转，定义了前序节点和当前节点，逐步翻转，逐步后移，直到链表尾部。
题目二：链表内指定区间反转
![链表内指定区间反转示意图]
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode 类
* @param m int 整型
* @param n int 整型
* @return ListNode 类
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
// 定义一个表头
ListNode* res = new ListNode(-1);
res->next = head;
// 定义前序节点
ListNode* per = res;
// 定义当前节点
ListNode* cur = head;
// 找到 m 位置
for(int i = 1; i < m; i++) {
per = cur;
cur = cur->next;
}
// 从 m 反转到 n
for(int i = m; i < n; i++) {
ListNode* temp = cur->next; // 记录当前节点下一个节点
cur->next = temp->next; // 越过当前节点
temp->next = per->next; // 当前节点反转
per->next = temp; // 前序节点连到最后
}
// 返回去掉表头
return res->next;
}
};
理解起来比较抽象，建议多写几遍加深记忆。
![手绘理解图]
题目三：链表中的节点每 k 个一组翻转
![链表 k 组翻转示意图]
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode 类
* @param k int 整型
* @return ListNode 类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// 找到每次反转的尾部
ListNode* tail = head;
// 遍历 k 次找到当前组的尾部
for(int i = 0; i < k; i++) {
if(tail == nullptr) return head;
tail = tail->next;
}
// 定义所需的前序节点和当前节点
ListNode* per = nullptr;
ListNode* cur = head;
while(cur != tail) {
ListNode* temp = cur->next;
cur->next = per;
per = cur;
cur = temp;
}
head->next = reverseKGroup(tail, k);
return per;
}
};
总结：
- 定义一个尾部，遍历 k 找到当前组的队尾（如果遍历时剩下的不足 k 个，则直接返回最后一组的 head）
- 定义前序、当前节点，对当前小组进行翻转
- 记下当前组的 head（翻转前为头，现在是尾），给 head 赋值为递归函数的返回值（即下一组的头节点），递归传入当前 tail(指向当前组的下一个位置，即下一组的头部)
- 返回当前的首部
理解了也不难，总之还是要多写两遍。
题目四：合并两个排序的链表
![合并两个排序链表示意图]
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead1 ListNode 类
* @param pHead2 ListNode 类
* @return ListNode 类
*/
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* res = new ListNode(-1); // 定义一个表头
ListNode* tail = res; // 用来遍历的指针
while(pHead1 != nullptr && pHead2 != nullptr) {
if(pHead1->val < pHead2->val) {
tail->next = pHead1;
pHead1 = pHead1->next;
} else {
tail->next = pHead2;
pHead2 = pHead2->next;
}
tail = tail->next;
}
// 处理剩余的
if(pHead1 != nullptr) {
tail->next = pHead1;
} else {
tail->next = pHead2;
}
return res->next;
}
};
逻辑清晰，阅读代码即可理解。
题目五：合并 k 个已排序的链表
主要是递归和分治的一个思想，将链表数组不断等分，直到只剩最后两个数组，然后将这两个数组排序合并，在逐步回归合并。
![合并 k 个排序链表示意图]
主要难点就是递归合并，排序部分跟上一道题一模一样。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode 类 vector
* @return ListNode 类
*/
// 用来合并两个链表
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* res = new ListNode(-1); // 定义一个表头
ListNode* tail = res; // 用来遍历的指针
while(pHead1 != nullptr && pHead2 != nullptr) {
if(pHead1->val < pHead2->val) {
tail->next = pHead1;
pHead1 = pHead1->next;
} else {
tail->next = pHead2;
pHead2 = pHead2->next;
}
tail = tail->next;
}
if(pHead1 != nullptr) {
tail->next = pHead1;
} else {
tail->next = pHead2;
}
return res->next;
}
// 划分合并区间
ListNode* divideMerge(vector<ListNode*>& lists, int left, int right) {
if(left > right) return NULL;
else if(left == right) { // 正好剩下最后一个链表
return lists[left];
}
// 从中间分成两段
int mid = (left + right)/2;
return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
// k 个列表归并排序
return divideMerge(lists, 0, lists.size() - 1);
}
};
能看懂，但是自己完整写下来还是有困难，建议多加练习。