< Back





203. Remove Linked List Elements

Fairly simple question to answer. Given a linked list and a value, remove all the nodes that have the
given value. Intuition here is to maintain a prev node that will be used to unlink the node with the
given value. A gotcha is the fact that the linked list has a head node with the given value.

To remedy this, we use a dummy node that will act as a pseudo-head. The rest of the algorithm
requires us to maintain the last time we saw a node that isn't the given value - this will be prev.
curr will be used to evaluate if a node has the given value, and it will be subsequently unlinked.

The solution is as follows:


  class Solution:
      def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
          dummy = prev = ListNode(-1, head)
          curr = head

          while curr:
              if curr.val == val:
                  prev.next = curr.next
              else:
                  prev = curr
              curr = curr.next

          return dummy.next


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We maintain pointers that occupy constant space.