题目链接

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

提示

  • 列表中的节点数目在范围 [0, 10] 内
  • 1 <= Node.val <= 50

  • 0 <= val <= 50

    思路

    链表删除操作，为了方便，可以设置一个虚拟头结点。
    注：如果使用C++，记得手动释放空间。

    题解

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12.  public:
    13.   ListNode* removeElements(ListNode* head, int val) {
    14.       ListNode dummyHead;
    15.       dummyHead.next = head;
    16.       ListNode* cur = &dummyHead;
    17.       while (cur->next != nullptr) {
    18.           if (cur->next->val == val) {
    19.               ListNode* temp = cur->next;
    20.               cur->next = cur->next->next;
    21.               delete temp;
    22.           } else {
    23.               cur = cur->next;
    24.           }
    25.       }
    26.       return dummyHead.next;
    27.   }
    28. };

    复杂度分析

  • 时间复杂度：0203-移除链表元素 - 图1

  • 空间复杂度：0203-移除链表元素 - 图2