Delete the element with value X

Intuition

Traverse the linked list and check if the data in the current node matches the given value. If a match is found, remove this node by updating the previous node's next reference to point to the node following the current one. If the traversal completes without finding a match, the linked list remains unchanged.

Approach

Initialize a pointer to the head of the list and another to null. The first pointer will traverse the list, while the second keeps track of the node before the current node.
Traverse the linked list until the data in the current node matches the target value. Consider two scenarios:
- If a match is found:
  - Update the previous node’s reference to point to the node following the current one.
  - Release the memory occupied by the current node, effectively removing it from the list.
- If the traversal completes without finding a match:
  - No changes are made to the linked list.
Note: In languages with automatic garbage collection (e.g., Java, Python, JavaScript), explicit node deletion is unnecessary as the garbage collector will automatically reclaim memory that is no longer in use.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

// Solution class
class Solution {
public:
    // To delete a node with a specific value in a linked list
    ListNode* deleteNodeWithValueX(ListNode* &head, int X) {
        // Check if list is empty
        if (head == NULL)
            return head;

        // If first node has target value, delete 
        if (head->val == X) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            return head;
        }

        ListNode* temp = head;
        ListNode* prev = NULL;


        /*Traverse the list to find 
        the node with the target value*/
        while (temp != NULL) {
            if (temp->val == X) {
                // Adjust the pointers 
                prev->next = temp->next;
                // Delete node
                delete temp;
                return head;
            }
            prev = temp;
            temp = temp->next;
        }

        return head;
    }
};


// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list from a vector
    vector<int> arr = {0, 1, 2};
    int X = 1;
    ListNode* head = new ListNode(arr[0]);
    head->next = new ListNode(arr[1]);
    head->next->next = new ListNode(arr[2]);
    
    // Print the original list
    cout << "Original List: ";
    printLL(head);
    
    // Create a Solution object 
    Solution sol;
    head = sol.deleteNodeWithValueX(head, X);

    // Print the modified linked list
    cout << "List after deleting the given value: ";
    printLL(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;

    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

// Solution class
class Solution {
    // To delete a node with a specific value in a linked list
    public ListNode deleteNodeWithValueX(ListNode head, int X) {
        // Check if list is empty
        if (head == null)
            return head;

        // If first node has target value, delete
        if (head.val == X) {
            head = head.next;
            return head;
        }

        ListNode temp = head;
        ListNode prev = null;

        /* Traverse the list to find 
        the node with the target value */
        while (temp != null) {
            if (temp.val == X) {
                // Adjust the pointers
                prev.next = temp.next;
                return head;
            }
            prev = temp;
            temp = temp.next;
        }

        return head;
    }
}

// Main class
class Main {
    // Helper Function to print the linked list
    private static void printLL(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a linked list from an array
        int[] arr = {0, 1, 2};
        int X = 1;
        ListNode head = new ListNode(arr[0]);
        head.next = new ListNode(arr[1]);
        head.next.next = new ListNode(arr[2]);

        // Print the original list
        System.out.print("Original List: ");
        printLL(head);

        // Create a Solution object
        Solution sol = new Solution();
        head = sol.deleteNodeWithValueX(head, X);

        // Print the modified linked list
        System.out.print("List after deleting the given value: ");
        printLL(head);
    }
}
# Definition of singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # To delete a node with a specific value in a linked list
    def deleteNodeWithValueX(self, head, X):
        # Check if list is empty
        if head is None:
            return head
        
        # If first node has target value, delete
        if head.val == X:
            head = head.next
            return head
        
        temp = head
        prev = None
        
        ''' Traverse the list to find 
        the node with the target value '''
        while temp is not None:
            if temp.val == X:
                # Adjust the pointers
                prev.next = temp.next
                return head
            prev = temp
            temp = temp.next
        
        return head

# Helper Function to print the linked list
def printLL(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Create a linked list from a list
    arr = [0, 1, 2]
    X = 1
    head = ListNode(arr[0])
    head.next = ListNode(arr[1])
    head.next.next = ListNode(arr[2])

    # Print the original list
    print("Original List: ", end="")
    printLL(head)

    # Create a Solution object
    sol = Solution()
    head = sol.deleteNodeWithValueX(head, X)

    # Print the modified linked list
    print("List after deleting the given value: ", end="")
    printLL(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // To delete a node with a specific value in a linked list
    deleteNodeWithValueX(head, X) {
        // Check if list is empty
        if (head === null)
            return head;

        // If first node has target value, delete
        if (head.val === X) {
            head = head.next;
            return head;
        }

        let temp = head;
        let prev = null;

        /* Traverse the list to find 
        the node with the target value */
        while (temp !== null) {
            if (temp.val === X) {
                // Adjust the pointers
                prev.next = temp.next;
                return head;
            }
            prev = temp;
            temp = temp.next;
        }

        return head;
    }
}

// Helper Function to print the linked list
function printLL(head) {
    let current = head;
    while (current !== null) {
        process.stdout.write(current.val + " ");
        current = current.next;
    }
    console.log();
}

// Main function
let arr = [0, 1, 2];
let X = 1;
let head = new ListNode(arr[0]);
head.next = new ListNode(arr[1]);
head.next.next = new ListNode(arr[2]);

// Print the original list
console.log("Original List: ");
printLL(head);

// Create a Solution object
let sol = new Solution();
head = sol.deleteNodeWithValueX(head, X);

// Print the modified linked list
console.log("List after deleting the given value: ");
printLL(head);

Complexity Analysis:

Time Complexity: O(N) worst case, when the value is found at the tail, and O(1) best case, when the value is found at the head. Here N is the length of the linked list. Space Complexity: O(1) as no extra space used.

Problem List

Delete the element with value X

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code