📋前言
🏠 个人主页：@聆风吟的个人主页
🔥系列专栏：本期文章收录在专栏《剑指offer每日一练》中，大家有兴趣可以浏览和关注，后面将会持续更新更多精彩内容！
⏰寄语：少年有梦不应止于心动，更要付诸行动。
🎉欢迎大家关注🔍点赞👍收藏⭐️评论📝
🌈作者留言：文章创作不易，可能会有些地方出现错误，还希望广大读者们能够帮忙指出，让我们大家一起共同进步。
一. ⛳️删除链表的节点（题目难度：简单）
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
题目：
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
示例：
输入： head = [ 4, 5, 1, 9 ], val = 5
输出： [ 4, 1, 9 ]
解释： 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为4 -> 1 -> 9。
说明：
- 题目保证链表中节点的值互不相同
- 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
解题思路：
思路： 遍历链表，直到找到某结点 cur->val = val 时跳出循环。设目标结点 cur 的前驱节点为 pre，后继节点为 cur->next；执行 pre->next = cur->next，即可删除 cur 结点。
实现过程：
(1) 首先判断是否删除头结点，如果是直接返回 head->next；
(2) 初始化： pre = head，cur = head->next；
(3) 遍历寻找目标结点： 当 cur 为空 或 cur 结点的值等于 val 时跳出循环。
- 保存当前结点索引，即
pre = cur - 遍历下个结点，即
cur = cur->next
(4) 删除结点： 若 cur 指向某个结点，则执行 pre->next = cur->next；若 cur 指向 null，则执行代表链表不包含值为val的结点；
(5) 返回链表的头结点 head 即可。
c++代码：文章来源：https://www.toymoban.com/news/detail-720788.html
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
//判断是否删除头结点，如果是直接返回
if(head->val == val) return head->next;
//初始化
ListNode* pre = head;
ListNode* cur = head->next;
//遍历寻找目标结点
while(cur != nullptr && cur->val != val){
pre = cur;
cur = cur->next;
}
//删除结点
if(cur != nullptr) pre->next = cur->next;
//返回头结点
return head;
}
};
二. ⛳️训练计划 V（题目难度：简单）
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
题目：
某教练同时带教两位学员，分别以链表 l1、l2 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 null 。
示例：
输入： intersectVal = 8, listA = [ 4, 1, 8, 4, 5 ], listB = [ 5, 0, 1, 8, 4, 5 ], skipA = 2, skipB = 3
输出： Reference of the node with value = 8
解释： 第一个正式训练项目编号为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [ 4, 1, 8, 4, 5 ]，链表 B 为 [ 5, 0, 1, 8, 4, 5 ]。skipA 表示在 A 中，相交节点前有 2 个节点；skipB 表示在 B 中，相交节点前有 3 个节点。
限制：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
解题思路：
(1) 初始化： 构建两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点
(2) 同时对两个链表进行逐结点遍历：
- 当
node1到达链表headA的末尾时，重新定位到链表headB的头结点，然后继续遍历； - 当
node2到达链表headB的末尾时，重新定位到链表headA的头结点，然后继续遍历；
(2) 当它们相遇时，如果同时指向 nullptr，则没有公共结点；否则指向的结点即为第一个公共结点。
c++代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//初始化
ListNode* node1 = headA;
ListNode* node2 = headB;
//同时对两个链表进行逐结点遍历，判断是否有相遇
while(node1 != node2)
{
//当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点
node1 = (node1 != nullptr ? node1->next:headB);
//当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点
node2 = (node2 != nullptr ? node2->next:headA);
}
//返回
return node1;
}
};
⛺结尾
今天的内容就到这里了，你们都学会了吗？如果还有疑问的话请在评论区里多多提问，大家可以一起帮你解决，让我们共同进步。创作不易，如果对你有用的的话点个赞支持下作者，你们的支持是作者创作最大的动力。关注我不迷路，让我们下期再见✋✋。文章来源地址https://www.toymoban.com/news/detail-720788.html
到了这里，关于【剑指offer|图解|链表】删除链表的节点 + 训练计划 V的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
