Sponsored
Sponsored
This approach involves using a dummy node to handle the removal of nodes, including edge cases where the head node itself needs to be removed. We use a pointer to traverse the list, comparing each node's value with the target val. If the node needs to be removed, we adjust the pointers to skip the node. If not, we just move to the next node.
Time Complexity: O(n), where n is the number of nodes in the linked list, as we must traverse all nodes.
Space Complexity: O(1) because we are using constant extra space.
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode(int x) : val(x), next(NULL) {}
7};
8
9class Solution {
10public:
11 ListNode* removeElements(ListNode* head, int val) {
12 ListNode* dummy = new ListNode(0);
13 dummy->next = head;
14 ListNode* current = dummy;
15 while (current->next != nullptr) {
16 if (current->next->val == val) {
17 ListNode* temp = current->next;
18 current->next = current->next->next;
19 delete temp;
20 } else {
21 current = current->next;
22 }
23 }
24 ListNode* newHead = dummy->next;
25 delete dummy;
26 return newHead;
27 }
28};In this solution, we use a dummy node to avoid complications with removing the head of the list. A current pointer is used to iterate over the linked list. For each node, if the node's value is equal to val, we bypass it by adjusting the pointers. After traversal, the dummy node is deleted, and we return the new head of the linked list.
This approach employs a recursive strategy to tackle the problem. The idea is to attempt removing elements starting from the rest of the list and linking the current node to the result of this removal. If the head node itself needs removal, simply return the result of removing nodes from the rest of the list by moving the reference forward.
Time Complexity: O(n), as each node is processed exactly once.
Space Complexity: O(n), due to the recursion stack for n nodes in the longest path.
1
This solution employs a recursive function that processes the rest of the list first and then makes a decision about the current node. If the current node’s value matches val, the function returns the next node as the new head; otherwise, it returns itself linked to the result of the processed rest.