每天一算：Remove Linked List Elements
16lz
2021-01-22
LeetCode上第203号问题：Remove Linked List Elements
题目
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解题思路
主要考察了基本的链表遍历和设置指针的知识点。
定义一个虚拟头节点dummyHead，遍历查看原链表，遇到与给定值相同的元素，将该元素的前后两个节点连接起来，然后删除该元素即可。
动画演示
动画演示GIF有点大，请稍微等待一下加载显示^_^
动画演示参考代码
代码一
1// 203. Remove Linked List Elements
2// https://leetcode.com/problems/remove-linked-list-elements/description/
3// 使用虚拟头结点
4// 时间复杂度: O(n)
5// 空间复杂度: O(1)
6class Solution {
7public:
8 ListNode* removeElements(ListNode* head, int val) {
9
10 // 创建虚拟头结点
11 ListNode* dummyHead = new ListNode(0);
12 dummyHead->next = head;
13
14 ListNode* cur = dummyHead;
15 while(cur->next != NULL){
16 if(cur->next->val == val){
17 ListNode* delNode = cur->next;
18 cur->next = delNode->next;
19 delete delNode;
20 }
21 else
22 cur = cur->next;
23 }
24
25 ListNode* retNode = dummyHead->next;
26 delete dummyHead;
27
28 return retNode;
29 }
30};
代码二
用递归来解。
通过递归调用到链表末尾，然后回来，需要删的元素，将链表next指针指向下一个元素即可。
1class Solution {
2public:
3 ListNode* removeElements(ListNode* head, int val) {
4 if (!head) return NULL;
5 head->next = removeElements(head->next, val);
6 return head->val == val ? head->next : head;
7 }
8};
执行结果
执行结果我们会在每天早上8点30分准时推送一条LeetCode上的算法题目，并给出该题目的动画解析以及参考答案，每篇文章阅读时长为五分钟左右。
更多相关文章
- Python办公自动化｜光速对比并提取两份Word/Excel中的不同元素
- 动画: 快速排序 | 如何求第 K 大元素？
- PHP使用递归按层级查找数据（代码详解）
- PHP递归算法的应用（含示例）
- 什么是php递归
- php递归经典案例