leetcode-代码随想录-链表-移除链表元素

题目

链接：203. 移除链表元素 - 力扣（LeetCode）
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

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

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {}
};

思路 & 代码

1. 由于要删除的节点可能是头节点，所以为了方便采用 虚拟头节点 的方法来移除元素。
2. 设置虚拟头节点：ListNode* dummyHead = new ListNode(0);
3. 移除元素：找到目标val节点 的前一个节点 cur，将其指向下下一个节点cur->next = cur->next->next
4. 释放被移除元素的内存

注意点： 在判断cur->next或cur->val时，要先判断cur不为空，否则就是报空指针错误

#include <iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while(cur->next != nullptr){if(cur->next->val == val){ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;}else{cur = cur->next;}}head = dummyhead->next;delete dummyhead;return head;}
};void printLinkedList(ListNode* head){ListNode* cur = head;while(cur != nullptr) {cout << cur->val << " ";cur = cur->next;}cout << endl;
}int main() {int n, m;ListNode* dummyHead = new ListNode(0);while(cin >> n){if(n == 0){cout << "list is empty" << endl;continue;}ListNode* cur = dummyHead;while(n--){cin >> m;ListNode* newNode = new ListNode(m);cur->next = newNode;cur = cur->next;}}ListNode* head = dummyHead->next;delete dummyHead;printLinkedList(head);int val = 6;Solution obj;ListNode* result = obj.removeElements(head,val);printLinkedList(result);
}

时间复杂度: O(n)
空间复杂度: O(1)