Given a singly linked list node, and an integer target, return the same linked list with all nodes whose value is target removed.
Example 1
Inputnode = 0 → 1 → 1 → 2
target = 1
Output0 → 2
Delete a Node from Singly Linked List using Recursion
If current node is the target to remove, we simply remove it and the result will be calling the recursion on its next node. Otherwise, its next node will be recursive call until we reach the end.
1 2 3 4 5 6 7 8 9 10 11 12 13 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* solve(LLNode* node, int target) { if (!node) return NULL; if (node->val == target) return solve(node->next, target); node->next = solve(node->next, target); return node; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* solve(LLNode* node, int target) {
if (!node) return NULL;
if (node->val == target) return solve(node->next, target);
node->next = solve(node->next, target);
return node;
}The space complexity is O(N) due to Recursion. The time complexity is O(N) as we need to go through each node in the singly linked list for target node removal. For non-recursive approach to remove the node from the linked list, you can refer to this: How to Delete Node in a Linked List (Given Only Access to That Node)?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Compute the Nth Fibonacci Numbers using Iterative and Math Algorithms
Next Post: Recursive Algorithm to Compute the Linked List Jumps
