203. Remove Linked List Elements

Problem

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Thought Process

  • the regular case is simple.

e.g. to delete 6 below, we can use a node(delnode) to store 6’s next node

2->6->3

then 2’s next points to delnode’s next node, then 6’s next points to None

  • The tricky part is the edge case:
    • if the deleted node is None, then return None
    • if the deleted node is head, then delnode = head, delnode.next = head.next, then remove head
      • it’s possible that after nth deletion, the new head might still be the target node to be removed. Here we need a loop
      • also after deleting nodes, it’s possible that the linked list is empty, then return None

White Board

Below is the white board:

Code

class listNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def removeElements(self, head, val):
        if head is None:
            return head

        while(head is not None and head.val == val):
            delNode = head
            head = delNode.next
            delNode = None

        if head is None:
            return head

        curr = head

        while(curr.next is not None):
            if (curr.next.val == val):
                delNode = curr.next
                curr.next = delNode.next
                delNode = None
            else:
                curr = curr.next

        return head

Result1

Complexity

  • Time complexity is O(n)

Optimization

There are just way too many edge case evaluations in the above solution. One good solution is to introduce a dummy head whose next points to head

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

class Solution:
    def removeElement(self, head, val):
        dummyHead = ListNode(-1)
        dummyHead.next = head

        curr = dummyHead

        while curr.next is not None:
            if curr.next.val == val:
                delNode = curr.next
                curr.next = delNode.next
                delNode.next = None
            else:
                curr = curr.next

        return dummyHead.next

The Time complexity is also O(n), but there are much less operations

Result2