LeetCode每日一练 —— 203. 移除链表元素
🌟 前言
Wassup guys!我是Edison 😎
今天是 LeetCode 上的 leetcode 203. 移除链表元素
Let’s get it!
1. 题目分析
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足
Node.val == val
的节点,并返回 新的头节点 。
示例 1:
示例 2:
示例 3:
2. 题目图解
这道题很简单,还是采用 双指针 法,但是要考虑几种情况
(1)常规情况
(2)链表中有连续的 val
(3)头节点就是 val
🍑 常规情况
定义一个 prev 指针指向 NULL;再定义一个 cur 指针指向头节点
第 1 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 2 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 3 步:此时 cur 指向的元素等于 6,那么元素 6 置为 NULL,然后让 prev 的 next 指向元素 3,cur 的 next 也指向元素 3 (如图所示👇)
第 4 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 5 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 6 步:此时 cur 指向的元素等于 6,那么元素 6 置为 NULL,然后让 prev 的 next 指向 cur 的 next(如图所示👇)
第 7 步:当 cur 指向的元素为 空 时,循环就终止了(如图所示👇)
✨动图演示
🍑 连续 val 情况
还是定义一个 prev 指针指向 NULL;再定义一个 cur 指针指向头节点(如图所示👇)。
第 1 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 2 步:cur 指向的元素不等于 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 3 步:此时 cur 指向的元素等于 6,那么删除该元素,然后让 prev 的 next 指向 cur 的 next,cur 指向下一个元素(如图所示👇)
第 4 步:此时 cur 指向的元素还是等于 6,那么删除该元素,然后让 prev 的 next 指向 cur 的 next,cur 指向下一个元素(如图所示👇)
第 5 步:此时 cur 指向的元素还是等于 6,那么删除该元素,然后让 prev 的 next 指向 cur 的 next,cur 指向下一个元素(如图所示👇)
第 6 步:此时 cur 指向的元素不是 6,那么 prev 和 cur 依次向后挪动(如图所示👇)
第 7 步:此时 cur 指向的元素等于 6,那么删除该元素然后让 prev 的 next 指向 cur 的 next,cur 指向 空,终止循环(如图所示👇)
可以看到,如果链表中有连续的 val,那么做法也是和常规情况一样的。
🍑 头节点就为 val
还是定义一个 prev 指针指向 NULL;再定义一个 cur 指针指向头节点(如图所示👇)。
此时可以发现一个问题,如果是按照常规情况来算的是,cur 指向的元素等于 6,那么删除该元素,然后让 prev 的 next 指向 cur 的 next,cur 指向下一个元素。
但是此时 prev 指向的元素为 空, cur 的 next 怎么能够赋值给 空 呢?显然是不行的,得另想办法!
其实很简单,我们再定义一个 curHead 指针指向头节点(如图所示👇)。
这里直接用一个动图来演示整个过程👇
3. 代码实现
📝 接口代码
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* prev, *cur;
prev = NULL;
cur = head;
// 循环的结束条件就是cur等于空
while (cur) {
// cur不等于val
if (cur->val != val) {
prev = cur; //直接把cur的地址赋给prev,相当于把prev移动到cur的位置上
cur = cur->next; // cur也向后移动一个位置
}
else { // 当cur等于val
struct ListNode* curHead = cur->next;
// 为什么 curHead 的内容为 cur->next, 而不是cur呢?
// 假设头节点就等于val,那么删除val以后, 就相当于头删
// 头删之后,如果curHead是内容是cur的地址的话,那么久找不到后面的链表了
// 所以curHead存的应该是cur->next, 也就是第二个节点的地址
if (prev == NULL) { // 头节点为val为val的情况
free(cur); // 释放掉cur
head = curHead; // 更新头节点
cur = curHead; // 然后把新的头节点的地址赋给cur
}
else { // 头节点不为val为val的情况
free(cur); // 释放val元素
prev->next = curHead; // 因为curHead存的是cur的next,也就是cur的下一个节点的地址,所以直接赋给prev的next
cur = curHead; // 然后让cur指向下一个节点的地址
}
}
}
return head;
}
🌟 提交结果
相关文章
- LeetCode每日一练 —— 160. 相交链表
- LeetCode 21. 合并两个有序链表 题解 C++
- leetcode 21 -- Merge Two Sorted Lists
- leetcode:Merge k Sorted Lists
- LeetCode_贪心算法_简单_455.分发饼干
- LeetCode_双指针_中等_328.奇偶链表
- LeetCode_二叉树_前缀和_中等_437.路径总和 III
- LeetCode_双指针_区间问题_中等_986.区间列表的交集
- LeetCode刷题(16)【简单】移除链表元素&&回文链表&&删除链表中的结点
- LeetCode·每日一题·面试题 05.02. 二进制数转字符串·数学
- Leetcode(一)回文数
- 「LeetCode」82. 删除排序链表中的重复元素 II
- 「LeetCode」19. 删除链表的倒数第 N 个结点
- 「LeetCode」202. 快乐数
- LeetCode-83. 删除排序链表中的重复元素(java)
- LeetCode-21. 合并两个有序链表(Goland实现)
- LeetCode-876. 链表的中间结点(Goland实现)
- [LeetCode] 683. K Empty Slots K个空槽
- [LeetCode] 109. Convert Sorted List to Binary Search Tree 把有序链表转成二叉搜索树
- [LeetCode] 287. Find the Duplicate Number 寻找重复数
- [LeetCode] 117. Populating Next Right Pointers in Each Node II 每个节点的右向指针 II
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项 II
- [LeetCode] 8. String to Integer (atoi) 字符串转为整数
- leetcode 121 买卖股票的最佳时机
- leetcode 704 二分查找