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/

题意

给定一个链表，然后删除值为val的结点。

题解

通俗的做法大家肯定都知道，就是直接判断当前结点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日星期一