You are asked to remove all elements of value val from a integer linked list. For example,
Remove 2 from the following list,
1 -> 2 -> 2 -> 1
becomes:
1 -> 1
Recursion
We represent the singly linked list (of type integer) using the following data structure:
1 2 3 4 5 6 7 8 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ |
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/and we have a helpful recursion function to remove one element:
1 2 3 4 5 6 | ListNode* removeElements(ListNode* head, int val) { if (head == NULL) return NULL; if (val == head->val) return removeElements(head->next, val); head->next = removeElements(head->next,val); return head; } |
ListNode* removeElements(ListNode* head, int val) {
if (head == NULL) return NULL;
if (val == head->val) return removeElements(head->next, val);
head->next = removeElements(head->next,val);
return head;
}The beauty of Recursion is its simplicity in expressing the algorithm.
Iterative
The iterative approach has to take care if the first few nodes are equal to val, in which case the head to return has to be updated. We then keep a prev node that is used to re-point the next once a node is found to be removed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: ListNode* removeElements(ListNode* head, int val) { // find the first head that does not equal to val while (head && (head->val == val)) { head = head->next; } if (head == NULL) { return NULL; } auto p = head; ListNode* prev = head; p = p->next; while (p) { if (p->val == val) { // update the link prev->next = p->next; } else { prev = p; } p = p->next; } return head; } }; |
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// find the first head that does not equal to val
while (head && (head->val == val)) {
head = head->next;
}
if (head == NULL) {
return NULL;
}
auto p = head;
ListNode* prev = head;
p = p->next;
while (p) {
if (p->val == val) { // update the link
prev->next = p->next;
} else {
prev = p;
}
p = p->next;
}
return head;
}
};Both approach has time complexity O(n) while the recursion generally requires the usage of a stack.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
365 wordsloading...
Last Post: How to Cache WeChat Token via PHP?
Next Post: Number of Solutions for Math Equations: 3x + y = 5702
Memory Leak!