【手撕力扣链表题】移除链表元素,反转链表(6/98)
💟作者简介：大家好，我是锡兰Ceylan_，可以叫我CC ❣️
📝个人主页：锡兰Ceylan_的博客
🏆博主信息：平凡的大一学生，有着不平凡的梦专栏
- 【备战蓝桥，冲击省一】
- 【开卷数据结构】
⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努努力💪
目前进度：
目录
🌺203. 移除链表元素
🍁题目描述
🍁基础框架
🍁详细思路
🍀思路一【迭代】
🍀思路二【递归】
🌺206. 反转链表
🍁题目描述
🍁基础框架
🍁详细思路
🍀思路一【迭代】
🍀思路二【递归】
🌺203. 移除链表元素
🍁题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1
输出：[]示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]提示：
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
🍁基础框架
- C++ 版本给出的基础框架代码如下：
/** * 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* removeElements(ListNode* head, int val) { }};
🍁详细思路
🍀思路一【迭代】
用 temp表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。
💬 代码演示
/** * 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* removeElements(ListNode* head, int val) { struct ListNode* Head = new ListNode(0, head); struct ListNode* temp = Head; while (temp->next != NULL) { if (temp->next->val == val) { temp->next = temp->next->next; } else { temp = temp->next; } } return Head->next; }};
🍀思路二【递归】
递归三部曲
- 递归结束条件
- 找到函数的等价关系式
- 调用函数
（1）当head为空时返回head
（2）不为空时，递归地进行删除操作。
（3）调用函数
💬 代码演示
class Solution {public: ListNode* removeElements(ListNode* head, int val) { if (head == nullptr) { return head; } head->next = removeElements(head->next, val); return head->val == val ? head->next : head; }};
🌺206. 反转链表
🍁题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
🍁基础框架
- C++ 版本给出的基础框架代码如下：
/** * 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* reverseList(ListNode* 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* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }};🍀思路二【递归】
递归三部曲
- 递归结束条件，
- 找到函数的等价关系式
- 调用函数
（1）当头结点或第二个结点为空的时候，返回头结点
（2）在返回的过程中，让当前结点的下一个结点的next指向当前结点，当前结点的next指向NULL，实现局部翻转。
（3）调用函数
本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪