MENU

LeetCode203. Remove Linked List Elements(链表 / 模拟)

2019 年 03 月 04 日 • 阅读: 1019 • LeetCode阅读设置

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日 星期一
最后编辑于: 2020 年 04 月 24 日