Katkat
Back

Remove nodes with a given value

Capital OneSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate singly linked lists, specifically handling edge cases like removing head nodes and reassigning pointers in a single pass.

Problem Statement

Given the head of a singly linked list and an integer val, remove all nodes of the linked list that have node.val == val and return the new head of the list.

Function Signature

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeElements(head: ListNode, val: int) -> ListNode:
    pass

Examples

Example 1: Input: head = [1, 2, 6, 3, 4, 5, 6], val = 6 Output: [1, 2, 3, 4, 5] Explanation: The nodes with value 6 are removed.

Example 2: Input: head = [7, 7, 7, 7], val = 7 Output: [] Explanation: All nodes are removed.

Constraints

  • The number of nodes in the list is in the range [0, 10^4].
  • 0 <= Node.val <= 50
  • 0 <= val <= 50

Edge Cases to Consider

  • An empty linked list (head is None).
  • A list where all nodes have the target value.
  • A list where the first node (or consecutive first nodes) have the target value.

Hints

Hint 1

Consider using a 'dummy' node that points to the head to simplify cases where the head itself needs to be removed.

Hint 2

Use a pointer to traverse the list and check the value of the `next` node rather than the current node.

Hint 3

If the `next` node matches the target value, skip it by updating the current node's `next` pointer to `current.next.next`.

Follow-up questions

  • Can you solve this problem recursively without using a dummy node?
  • What are the space and time complexity requirements for your solution, and can it be done in O(1) auxiliary space?
  • How would your approach change if this were a doubly linked list instead of a singly linked list?