前言
在本章节中,我们将一起学习几道经典的链表相关 OJ 算法题,通过实际题目练习来巩固链表的核心知识点与编程技巧。
📚 初阶数据结构
-【 单链表 】----
【题目链接】:https://leetcode.cn/problems/remove-linked-list-elements/description/

【算法原理】:
1、原地删除
用cur遍历链表,遇到值为val的节点,直接删除,但是牵扯到删除cur后就找不到后面的节点了,因此我们需要一个prev指针去记录cur节点的前一个节点,让prev和cur同步遍历
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* prev = NULL; // 用于记录当前节点cur的前一个节点,初始化为NULL(表示cur初始无前驱)
ListNode* cur = head; // 用于遍历链表的当前节点,从链表头开始
// 遍历整个链表,直到cur为NULL(链表结束)
while(cur)
{
// 情况1:当前节点的值等于要删除的val
if(cur->val == val)
{
// 子情况1:当前节点是头节点(prev为NULL,说明cur没有前驱)
if(prev == NULL)
{
head = cur->next; // 头节点更新为当前节点的下一个节点(跳过当前节点)
delete cur; // 释放当前节点的内存
cur = head; // cur移动到新的头节点,继续遍历
}
// 子情况2:当前节点不是头节点(有前驱节点prev)
else
{
prev->next = cur->next; // 前驱节点的next直接指向当前节点的下一个节点(跳过当前节点)
delete cur; // 释放当前节点的内存
cur = prev->next; // cur移动到前驱节点的下一个节点(即原当前节点的下一个节点),继续遍历
}
}
// 情况2:当前节点的值不等于val,无需删除,继续向前遍历
else
{
prev = cur; // prev更新为当前节点(成为下一个节点的前驱)
cur = cur->next; // cur移动到下一个节点
}
}
// 遍历结束,返回修改后的链表头节点
return head;
}
};2、创建新链表
创建一个新链表,让值不为val的节点尾插到新链表,值为val的节点释放掉
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* Newhead = nullptr; // 新链表的头节点(最终要返回的结果)
ListNode* cur = head; // 用于遍历原链表的当前节点指针
ListNode* tail = nullptr; // 指向新链表的尾节点,方便尾插法添加节点
// 遍历原链表的所有节点
while (cur) {
// 如果当前节点的值不是要删除的目标值,就加入新链表
if (cur->val != val) {
// 新链表为空时,当前节点既是头也是尾
if (Newhead == nullptr) {
Newhead = tail = cur;
} else {
// 新链表非空时,把当前节点接到尾节点后面,再更新尾节点
tail->next = cur;
tail = tail->next;
}
// 移动到原链表的下一个节点
cur = cur->next;
} else {
// 如果是要删除的节点,先保存下一个节点的地址
ListNode* next = cur->next;
// 释放当前节点的内存
delete cur;
// 移动到下一个节点继续遍历
cur = next;
}
}
// 遍历结束后,新链表的尾节点要断开与原链表剩余节点的连接(防止野指针)
if (tail) {
tail->next = nullptr;
}
// 返回新链表的头节点
return Newhead;
}
};【题目链接】:https://leetcode.cn/problems/reverse-linked-list/

【算法原理】:
1、原地操作
通过n1、n3这两个节点辅助,改变n2的链接关系,例:n2->next指向n1,同时向后面移动一个位置,重复操作就可以达到逆置的效果

class Solution {
public:
ListNode* reverseList(ListNode* head)
{
if (head == nullptr) // 空链表直接返回nullptr
return nullptr;
ListNode* n1 = nullptr; // 指向反转后链表的前一个节点(初始为nullptr,对应原链表头的前序)
ListNode* n2 = head; // 指向当前需要反转的节点(初始为原链表头)
ListNode* n3 = head->next; // 保存当前节点的下一个节点(防止反转后断链)
// 遍历原链表,直到当前节点n2为空
while (n2)
{
n2->next = n1; // 反转当前节点的指向(指向n1,即前一个节点)
// 三个指针依次后移,准备处理下一个节点
n1 = n2;
n2 = n3;
if (n3) // 若n3不为空,继续后移(避免空指针访问)
n3 = n3->next;
}
return n1; // 循环结束后,n1即为反转后链表的头节点
}
};2、创建新链表
用cur遍历链表,进行新链表的头插操作
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
ListNode* cur = head; // 用于遍历原链表的当前节点
ListNode* newhead = nullptr; // 反转后新链表的头节点(初始为空)
// 遍历原链表所有节点
while (cur)
{
ListNode* next = cur->next; // 保存当前节点的下一个节点(防止断链)
cur->next = newhead; // 反转当前节点指向(指向新链表的头)
newhead = cur; // 更新新链表头为当前节点(当前节点成为新的头)
cur = next; // 移动到原链表的下一个节点继续处理
}
return newhead; // 最终newhead即为反转后链表的头节点
}
};【题目链接】:https://leetcode.cn/problems/middle-of-the-linked-list/description/

【算法原理】:
创建两个指针,一个一次走两步,一个一次走一步,走的快的到结尾了,走的慢的就到链表中间了,但是这个题要注意边界问题,如果链表节点个数为偶数的话,fast最终会走到尾节点的下一个位置,为奇数的话走到最后一个节点
class Solution {
public:
ListNode* middleNode(ListNode* head)
{
ListNode* slow = head; // 慢指针:每次移动1步
ListNode* fast = head; // 快指针:每次移动2步
// 当快指针未走到链表末尾(快指针本身非空且下一个节点非空)
while (fast && fast->next)
{
fast = fast->next->next; // 快指针走2步
slow = slow->next; // 慢指针走1步
}
// 循环结束后,慢指针恰好指向中间节点
// (若节点数为奇数,指向正中间;若为偶数,指向第二个中间节点)
return slow;
}
};题目描述:输入一个链表,输出该链表中倒数第 k 个节点。为了符合大多数人的习惯,本题从 1 开始计数,即链表的尾节点是倒数第 1 个节点。 例如,一个链表有
6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例 1: 输入:head = [1,2,3,4,5], k = 2输出:[4,5]解释:链表的倒数第 2 个节点是值为 4 的节点,其后续节点为 5,故输出[4,5]。 示例 2: 输入:head = [1], k = 1输出:[1]示例 3: 输入:head = [1,2], k = 3输出:null解释:链表长度为 2,k = 3 超出范围,返回null。
【算法原理】:
依旧快慢指针,让快指针先走k步,这个时候快慢指针之间的距离就是k,然后快指针走到空时,慢指针的位置就是倒数第k个节点的位置,如果fast提前变成空了,说明k超出范围了,直接返回空
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
// 处理空链表的情况
if (head == nullptr)
{
return nullptr;
}
// 初始化快慢指针,均指向头节点
ListNode* fast = head;
ListNode* slow = head;
// 快指针先向前走k步
for (int i = 0; i < k; ++i)
{
// 若快指针提前为空,说明k超过链表长度
if (fast == nullptr)
{
return nullptr;
}
fast = fast->next;
}
// 快慢指针同步移动,直到快指针到达末尾
while (fast != nullptr)
{
fast = fast->next;
slow = slow->next;
}
// 此时慢指针指向倒数第k个节点
return slow;
}
};【题目链接】:https://leetcode.cn/problems/merge-two-sorted-lists/description/

【算法原理】:
这道题咱们就不原地处理了,原地处理会很麻烦,而且很难想清楚
所以我们直接创建个新链表,遍历两个原链表,小的尾插到新链表,我会用两种方式演示这个思路
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 若其中一个链表为空,直接返回另一个链表
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
ListNode* cur1 = list1; // 遍历list1的指针
ListNode* cur2 = list2; // 遍历list2的指针
ListNode* head = nullptr; // 合并后新链表的头节点
ListNode* tail = nullptr; // 合并后新链表的尾节点,用于尾插
// 同时遍历两个链表,直到其中一个遍历完毕
while (cur1 && cur2) {
// 选取值较小的节点接入新链表
if (cur1->val < cur2->val) {
// 新链表为空时,当前节点既是头也是尾
if (head == nullptr) {
head = tail = cur1;
} else {
// 新链表非空时,尾插当前节点并更新尾指针
tail->next = cur1;
tail = tail->next;
}
cur1 = cur1->next; // 移动list1的遍历指针
} else {
// 逻辑同上,处理list2的节点
if (head == nullptr) {
head = tail = cur2;
} else {
tail->next = cur2;
tail = tail->next;
}
cur2 = cur2->next; // 移动list2的遍历指针
}
}
// 若list1还有剩余节点,直接接到新链表尾部
if (cur1) {
tail->next = cur1;
}
// 若list2还有剩余节点,直接接到新链表尾部
if (cur2) {
tail->next = cur2;
}
return head; // 返回合并后链表的头节点
}
};这个写法没有哨兵位,我下面写个有哨兵位的写法,写完大家可以对比下区别
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 若其中一个链表为空,直接返回另一个链表
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
ListNode* cur1 = list1; // 遍历list1的指针
ListNode* cur2 = list2; // 遍历list2的指针
ListNode* head = new ListNode(); // 哨兵节点(简化头节点处理)
ListNode* tail = head; // 指向新链表尾部,用于尾插
// 同时遍历两个链表,选取较小节点接入新链表
while (cur1 && cur2) {
if (cur1->val < cur2->val) {
tail->next = cur1; // 接入list1当前节点
tail = tail->next; // 尾指针后移
cur1 = cur1->next; // 移动list1遍历指针
} else {
tail->next = cur2; // 接入list2当前节点
tail = tail->next; // 尾指针后移
cur2 = cur2->next; // 移动list2遍历指针
}
}
// 拼接剩余节点(其中一个链表已遍历完)
if (cur1) {
tail->next = cur1;
}
if (cur2) {
tail->next = cur2;
}
// 哨兵节点的下一个才是真正的头节点,释放哨兵节点避免内存泄漏
ListNode* newhead = head->next;
delete head;
return newhead; // 返回合并后链表的头节点
}
};经过对比发现,有哨兵位的链表尾插时不用处理头节点为空的情况,会方便一点
以上是链表OJ前5个题,下一篇文章会再讲解5个链表相关OJ题!!!