Solution: Removing Nodes From Linked List

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Removing Nodes From Linked List

Table of Contents

Contents are not accessible

Problem Statement

Write Recursive Approach for Removing Nodes From Linked List.

Given a singly linked list and a target value, write a recursive algorithm to remove all nodes from the linked list that have the target value.

Examples:

Sr #	Input	Expected Output	Description
1	`1 -> 2 -> 3 -> 4 -> 2`	`1 -> 3 -> 4`	Remove all nodes with value `2` from the list.
2	`2 -> 2 -> 2 -> 2 -> 2`	`null`	Remove all nodes with value `2` from the list.
3	`1 -> 3 -> 5 -> 7`	`1 -> 3 -> 5 -> 7`	No nodes with value `2` exist in the list.

Constraints:

The number of the nodes in the given list is in the range [1, 10<sup>5</sup>].
1 <= Node.val <= 10<sup>5</sup>

Solution:

The algorithm follows a recursive approach to remove nodes with the target value from the linked list. The key steps are as follows:

If the linked list is empty, return null.
Recursively traverse the linked list, moving to the next node.
If the current node has the target value, skip it and return the result of the recursive call on the next node.
If the current node does not have the target value, set its next pointer to the result of the recursive call on the next node.
Return the current node as the new head of the modified linked list.

Code

Here is the code for this algorithm:

Python3

. . . .

Space and Time Complexity

The time complexity of the algorithm is $O(N)$ , where n is the number of nodes in the linked list. This is because the algorithm needs to visit each node once to remove nodes with the target value.

The space complexity of the algorithm is $O(N)$ , where n is the number of recursive calls on the stack. This is because for each recursive call, additional stack space is required to store the function call context. In the worst case, when all nodes have the target value, the recursion depth is n, resulting in $O(N)$ space complexity.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible