# LeetCode203. Remove Linked List Elements（链表 / 模拟）

## LeetCode203. Remove Linked List Elements（模拟）

• Easy
• Accepted：207,080
• Submissions：587,366

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

### 链接

https://leetcode.com/problems/remove-linked-list-elements/

### 题解

• 通俗的做法大家肯定都知道，就是直接判断当前结点curNode指向的下一个结点curNode->next的值是否等于val（cur->next->val == val），如果等于那么就把curNode指向curNode->next指向的下一个结点，即curNode->next = curNode->next->next，但是有一个问题就是需要单独判断头结点。
• 实际上我们可以增加一个虚拟头结点virtualHead，virtualHead->next=head，然后就把判断“合二为一”，无需再单独考虑头结点，最后返回的是virtualHead->next
• 此外还有一些问题就是需要判断删除前或者删除后的链表是否为空。
• 最好对自己申请的空间手动删除。
• 均为线性时间复杂度。

### 代码

• Runtime: 32 ms, faster than 100.00% of C++ online submissions for Remove Linked List Elements.
• Memory Usage: 11.4 MB, less than 40.51% of C++ online submissions for Remove Linked List Elements.
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {

// 对头结点特殊处理
while (head != NULL && head->val == val)
{
ListNode* node = head;
head = head->next;
delete node;
}

if (head == NULL)
return head;

// 考虑下一个结点的值是否等于val
ListNode* curNode = head;
while (curNode->next != NULL)
{
if (curNode->next->val == val)
{
ListNode* delNode = curNode->next;
curNode->next = delNode->next;
delete delNode;
}
else
curNode = curNode->next;
}

return head;
}
};
• Runtime: 32 ms, faster than 100.00% of C++ online submissions for Remove Linked List Elements.
• Memory Usage: 11.6 MB, less than 8.86% of C++ online submissions for Remove Linked List Elements.
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* virtualHead = new ListNode(0);
virtualHead->next = head;

ListNode* curNode = virtualHead;
while (curNode->next != NULL)
{
if (curNode->next->val == val)
{
ListNode* delNode = curNode->next;
curNode->next = delNode->next;
delete  delNode;
}
else
curNode = curNode->next;
}

// delete virtualHead;
return virtualHead->next;
}
};

The end.
2019年3月4日 星期一