每天一算：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有点大，请稍微等待一下加载显示^_^

参考代码

代码一

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

执行结果