Knowledge Guide
Home › DSA › Recursion

Solution Removing Nodes From Linked List

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 #InputExpected OutputDescription
11 -> 2 -> 3 -> 4 -> 21 -> 3 -> 4Remove all nodes with value 2 from the list.
22 -> 2 -> 2 -> 2 -> 2nullRemove all nodes with value 2 from the list.
31 -> 3 -> 5 -> 71 -> 3 -> 5 -> 7No nodes with value 2 exist in the list.

Constraints:

Solution:

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

  1. If the linked list is empty, return null.
  2. Recursively traverse the linked list, moving to the next node.
  3. If the current node has the target value, skip it and return the result of the recursive call on the next node.
  4. 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.
  5. Return the current node as the new head of the modified linked list.
Image
Image

Code

Here is the code for this algorithm:

java
// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int val) {
//         this.val = val;
//     }
// }

public class Solution {

  public static ListNode removeNodes(ListNode head, int target) {
    // Base case: If the list is empty, return null
    if (head == null) {
      return null;
    }

    // Recursively remove nodes with target value from the remaining list
    head.next = removeNodes(head.next, target);

    // Check if the current node has the target value
    if (head.val == target) {
      // Skip the current node and return the modified list
      return head.next;
    }

    // Return the current node as the new head of the modified list
    return head;
  }

  public static void printLinkedList(ListNode head) {
    ListNode current = head;
    while (current != null) {
      System.out.print(current.val + " ");
      current = current.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Example 1
    ListNode head1 = new ListNode(1);
    head1.next = new ListNode(2);
    head1.next.next = new ListNode(3);
    head1.next.next.next = new ListNode(4);
    head1.next.next.next.next = new ListNode(2);

    System.out.print("Original Linked List 1: ");
    printLinkedList(head1);

    // Remove nodes with value 2 from linked list
    ListNode modifiedHead1 = removeNodes(head1, 2);
    System.out.print("Modified Linked List 1: ");
    printLinkedList(modifiedHead1);

    // Example 2
    ListNode head2 = new ListNode(2);
    head2.next = new ListNode(2);
    head2.next.next = new ListNode(2);
    head2.next.next.next = new ListNode(2);
    head2.next.next.next.next = new ListNode(2);

    System.out.print("Original Linked List 2: ");
    printLinkedList(head2);

    // Remove nodes with value 2 from linked list
    ListNode modifiedHead2 = removeNodes(head2, 2);
    System.out.print("Modified Linked List 2: ");
    printLinkedList(modifiedHead2);

    // Example 3
    ListNode head3 = new ListNode(1);
    head3.next = new ListNode(3);
    head3.next.next = new ListNode(5);
    head3.next.next.next = new ListNode(7);

    System.out.print("Original Linked List 3: ");
    printLinkedList(head3);

    // Remove nodes with value 2 from linked list
    ListNode modifiedHead3 = removeNodes(head3, 2);
    System.out.print("Modified Linked List 3: ");
    printLinkedList(modifiedHead3);
  }
}

Space and Time Complexity

The time complexity of the algorithm is , 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 , 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 space complexity.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Removing Nodes From Linked List? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Removing Nodes From Linked List** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Removing Nodes From Linked List** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Removing Nodes From Linked List**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Removing Nodes From Linked List**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Depth First SearchSolution Fibonacci Series Using Me →