目录
0 容易被大家忽略的问题
为什么一些对链表操作的函数，需要新建一个节点指针然后再去对链表操作呢？
例如写了一个遍历链表的函数，传入head指针。如果我们直接对 head 指针进行操作遍历。就需要 head = head→next 然后遍历下一个节点的值。此时就改变了head的指向，等遍历完之后head就变成一个空指针了，然后你发现操作完链表。
1 移除链表元素
- 🎈 文档讲解：
- 🎈 视频讲解：
- 🎈 做题状态：感觉很挫败，角色很简单的链表删除居然没做出来
1.1 开始的错误解题
其实我最开始的解题问题很大：
- 头结点的操作和其他节点是不一样的，这一点一开始没有思考到
- 头结点和头指针没有搞清楚，导致后面移动元素时一团糟。
1.2 头结点和头指针的区别
1.2.1 区别
在链表中，有两个概念：头结点和头指针。
头结点：
- 头结点是指链表中的第一个实际存储数据的节点。
- 有些链表的设计中会在头部额外添加一个节点，称为头结点，这个节点不存储任何数据，只是为了方便对链表的操作，例如在删除或插入节点时不需要特殊处理头节点的情况。
- 头结点并不一定是链表的第一个元素，它可以位于第一个元素之前，也可以位于第一个元素的位置。
头指针：
- 头指针是指向链表中第一个节点的指针。
- 头指针是为了能够方便地访问链表，它存储了链表的起始地址，通过头指针可以遍历整个链表。
- 在很多情况下，头指针也被用来代表整个链表本身，因此当我们传递链表作为参数时，通常传递的是头指针。
下面是头结点和头指针的示例：
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
int main() {
// 创建头结点
ListNode* head = new ListNode(-1); // 头结点不存储有效数据
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
head->next = node1;
node1->next = node2;
// 头指针指向链表的第一个节点
ListNode* headPtr = head;
// headPtr->next 其实就是 head->next。
std::cout << "headPtr->next = " << headPtr->next << std::endl;
std::cout << "head->next = " << head->next << std::endl;
// 但是 headPtr 指针和 head 头结点的地址是不同的
std::cout << "&headPtr = " << &headPtr << std::endl;
std::cout << "&head = " << &head << std::endl;
// 释放内存
delete node2;
delete node1;
delete head;
return 0;
}
在这个示例中，head是头指针，指向链表的第一个节点（头结点）。链表的头结点是一个额外添加的节点，用于简化对链表的操作（添加一个额外的头结点，也被称作虚拟头结点，可以让链表头部元素删除操作和其他元素删除操作保持一致）。
1.2.2 思考
在刚才的代码案例中 头指针和头结点的地址是不同的，但是 headPtr->next 和 head->next 是相同的。
head 是指向链表头结点的指针，而 headPtr 是指向head的指针。
1.3 正确的题解
1.3.1 直接移除法
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 直接移除法
// 1. 先判断头结点是目标节点的情况
while (head && head->val == val)
{
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 2. 移除非头结点
ListNode* cur = head;
while (cur && cur->next)
{
if (cur->next->val == val)
{
// 创建一个临时指针指向待删除的内存
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else
{
cur = cur->next;
}
}
return head;
}
};
首先通过遍历的方式将头结点是目标元素的值移除完，然后再考虑后序的情况。 下面是几个易混淆的值
- head->val 是第一个节点的值
- head->next 存储的是下一个节点
- head->next->val 存储的是下一个节点的值
※※ 然后有个很重要的点需要弄清楚，就是
cur指针指向的是哪个位置，此时头结点已经全部判断并移除完毕了，可以确定第一个节点肯定不是目标值。那么cur指针是从第一个节点开始移动呢？（也就是ListNode* cur = head->next;）还是从第二个节点开始移动呢？（ListNode* cur = head;）
- 假如
cur指针从第二个节点开始移动，那么第二个节点就需要判断自己是不是目标值，然后如果是的话，要将该节点移除。也就是找到当前节点的上个节点，但是我们此时已经找不到上个节点的信息了，因为我们是单向链表，只能一直向后遍历。- 假如
cur指针从第一个节点开始移动，那么就去判断cur->next->val == val是否为目标值，如果是的话，那么就将cur->next = cur->next->next;此时删除操作就完成了。
1.3.2 添加虚拟头节点辅助移除法
链表的删除操作，头结点和非头结点是不同的，但是可以通过创建一个虚拟头结点，然后达到头结点和其他节点一样的删除操作。
现在添加了一个新的虚拟头结点，那么此时 cur 指针可以直接指向虚拟头结点，然后判断虚拟头结点的下一个节点是否需要移除（也就是实际存储数据的第一个节点）。
ListNode* removeElements(ListNode* head, int val)
{
// 虚拟头结点法
// 1. 创建一个虚拟头结点，然后指向第一个节点位置
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode* cur = dummyNode;
// 2. 遍历
while (cur && cur->next)
{
if (cur->next->val == val)
{
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else
{
cur = cur->next;
}
}
// 3. 返回更新后的头结点指针，注意不是返回head，因为头结点可能被移除，此时因该返回 虚拟头结点指向的下一个节点
return dummyNode->next;
}
1.3.3 总结
- 直接移除法的是分头结点和非头结点两种情况进行操作。（cur 指针从head开始遍历）
- 虚拟头结点法是在第一个节点前添加一个虚拟头结点，让头结点和非头节点操作保持一致。（cur指针从dummyHead开始遍历）
2 设计链表
- 🎈 文档讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
- 🎈 视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
- 🎈 做题状态：一定要注意虚拟头结点
2.1 我的解题
采用虚拟头结点的方式解题，这样可以保证头结点和非头结点操作的一致性
如下图： cur 是当前指针， dummy 是虚拟头结点，这个节点指向的下一个节点是第一个节点。在解题过程中一定要注意当前指针 cur 指向的是哪里，同时搞清楚当前指针和第一个节点的关系。
【注意】： dummy->next 返回的才是第一个节点，一定要记清楚。
class MyLinkedList {
public:
struct LinkNode
{
int val;
LinkNode* next;
LinkNode(int val) : val(val), next(nullptr) {}
};
MyLinkedList() {
dummyHead = new LinkNode(0);
size = 0;
}
int get(int index) {
// 如果 index 不在 区间内直接返回-1
if (index > size - 1 || index < 0) return -1;
LinkNode* cur = dummyHead->next;
for (int i = 0; i < index; i++)
{
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkNode* newNode = new LinkNode(val);
newNode->next = dummyHead->next;
dummyHead->next = newNode;
size++;
}
void addAtTail(int val) {
LinkNode* cur = dummyHead;
for (int i = 0; i < size; i++)
{
cur = cur->next;
}
// 遍历完后，cur指向最后一个节点
LinkNode* newNode = new LinkNode(val);
cur->next = newNode;
size++;
}
void addAtIndex(int index, int val) {
// 当index等于size时，插入链表末尾
if (index == size)
{
addAtTail(val);
return;
}
if (index > size || index < 0) return;
// 当index是一个有效值时，将新的节点插入index下标之前
LinkNode* cur = dummyHead;
while (index > 0)
{
cur = cur->next;
index--;
}
// 在cur后面插入新的节点
LinkNode* newNode = new LinkNode(val);
newNode->next = cur->next;
cur->next = newNode;
size++;
}
void deleteAtIndex(int index) {
// 先判断index是否有效
if (index > size - 1 || index < 0) return;
LinkNode* cur = dummyHead;
while (index > 0)
{
cur = cur->next;
index--;
}
// 此时cur指向了要删除元素的前一个节点
LinkNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
size--;
}
private:
LinkNode* dummyHead;
int size;
};
3 反转链表
- 🎈 文档讲解：
- 🎈 视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
- 🎈 做题状态：翻转链表其实就是遍历链表元素，然后插入新链表的头部
3.1 我的解题
注意，reverseHead 是一个虚拟头结点，所以返回的时候是返回 reverseHead->next 。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 翻转链表其实就是遍历链表元素，然后插入新链表的头部
ListNode* reverseHead = new ListNode(0);
if (head == nullptr) return head;
ListNode* cur = head;
while (cur)
{
// 将cur当前的值保存到新链表中
ListNode* newNode = new ListNode(cur->val);
newNode->next = reverseHead->next;
reverseHead->next = newNode;
cur = cur->next;
}
return reverseHead->next;
}
};
3.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);
}
};
