每天一算:Remove Linked List Elements

每天一算:Remove Linked List Elements

LeetCode上第203号问题:Remove Linked List Elements

题目

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6  
输出: 1->2->3->4->5

解题思路

主要考察了基本的链表遍历和设置指针的知识点。

定义一个虚拟头节点dummyHead,遍历查看原链表,遇到与给定值相同的元素,将该元素的前后两个节点连接起来,然后删除该元素即可。

动画演示

动画演示GIF有点大,请稍微等待一下加载显示^_^

每天一算:Remove Linked List Elements
动画演示

参考代码

代码一

 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};

执行结果

每天一算:Remove Linked List Elements
执行结果


我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

每天一算:Remove Linked List Elements
每天一算:Remove Linked List Elements

HELLO,小伙伴

长按二维码就可以关注我们拉!


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Remove Linked List Elements

我还会在以下平台发布内容

GitHub 哔哩哔哩