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

Discussion

This problem requires an algorithm scanning through the linked-list, removing desired node and reconstruct the links.

An intuitive approach would be scanning the value of the next node. If the next node is to-be-removed, we can reconstruct the link to the next-next node.

Yet a problem is that we can't filter out the node at the beginning if they are carrying the desired value.

There are different approach to do. Instead of creating a pesudo-node at the beginning, i cache the previously scanned node, and check current node's value.

Solution

The solution begins with a loop iterate through all the elements, and we keep update the cache to prepare to the link-reconstruction.

Once the desired value is scanned, we skip the cache update to skip it from reconstruction.

Besides we managed a variable cache_head, in order to return the Linked-List from the beginning.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        node = head
        cache = None
        cache_head = None

        while node:
            if node.val != val:
                if not cache:
                    cache_head = node
                    cache = node
                else:
                    cache.next = node
                    cache = node
            node = node.next

        if cache:
            cache.next = node

        return cache_head

Complexity Analysis

• Time Complexity: O(n), as only one scanning of the list is required.
• Space Complexity: O(1), as only two nodes are cached in memory.