Delete Node from Linked List

Delete nodes from a linked list with certain values.

The problem may be found on leetcode.

Analysis

First, if the head has a bad value it must be removed and the head should be updated to the next value. This process should repeat until a head with an acceptable value is found. This head is saved to be returned.

Once an acceptable head is found, unacceptable elements should be removed from the remainder of the array. This involves delinking the inadmissible node from its prior node, and linking the prior node to current nodes next node.

When delinking, the prior node (lastnode) will not be updated on the loop, as the current node (node) just delinked was the prior node. This is best explained visually:

Iteration before delinking of 2

--> 1 ----------> 2 -----------> 3 ----------> 4
    ^lastnode     ^node          ^node.next
                   =lastnode.next


Iteration after delinking of 2

--> 1 ----------> 3 -----------> 4
    ^lastnode     ^node          ^node.next


Iteration after checking 3

--> 1 ----------> 3 -----------> 4
                  ^lastnode      ^node

Solution

First, it is necessary to implement a linked list. This was done in the prompt, however I decided to add a bit more for my own tests:

class ListNode:
    val: int
    next: Self | None

    def __init__(self, val=0, next: Self | None = None):
        self.val = val
        self.next = next

    def __iter__(self):
        curr = self
        while curr is not None:
            yield curr.val
            curr = curr.next

    @classmethod
    def fromItems(cls, *items: int) -> Self:
        if not items:
            raise ValueError("At least one item is required.")

        head = cls(items[0])

        lastnode = head
        for k in range(len(items) - 1):
            item = items[k + 1]
            node = cls(item)
            lastnode.next = node
            lastnode = node

        return head

Then I implemented a solution roughly as described above.

class Solution:
    def modifiedList(
        self,
        nums: list[int],
        head: ListNode,
    ) -> Optional[ListNode]:

        hashed = set(nums)

        # NOTE: Remove any heads that have bad values.
        node = head
        nodelast: ListNode  # already checked
        while node is not None:
            if node.val not in hashed:
                break

            nodelast = node
            node = node.next  # type: ignore[assignment]

        head_final = node
        if head_final is None or head_final.next is None:
            return head_final

        # NOTE: Delink if value is bad. ``nodelast`` should not be incremented
        #       when a bad value is removed as it is will remain the same.
        while node is not None:

            if node.val in hashed:
                nodelast.next = node.next
                node = node.next  # type: ignore[assignment]
            else:
                nodelast = node
                node = node.next  # type: ignore[assignment]

        return head_final

This solution had \(99\%\) quantile runtime and a pathetic \(21\%\) quantile memory usage. This is likely due to using set to make it easier to search for illegal node values - completing the delinks improved the memory performance to the \(44\%\) quantile, a drastic improvement - however it was at the cost of one quantile of runtime. Removing the use of set resulted in the submission exceeding the time limit. The following solution includes delinking and combines both loops into a single while loop:

class Solution2:
    def modifiedList(
        self,
        nums: list[int],
        head: ListNode,
    ) -> Optional[ListNode]:

        # NOTE: Remove any heads that have bad values.
        hashed = set(nums)
        head_final = None
        is_head = True
        node = head
        nodelast: ListNode

        while node is not None:
            if is_head:
                if node.val not in hashed:
                    head_final = node
                    is_head = False
                    continue

                nodelast = node
                node = node.next  # type: ignore[assignment]
                nodelast.next = None
            elif node.val in hashed:
                nodelast.next = node.next
                node.next = None

                node = nodelast.next  # type: ignore[assignment]
            else:
                nodelast = node
                node = node.next  # type: ignore[assignment]

        return head_final

This did drastically improve the memory usage - all the way to the \(71\%\) quantile - however this reduces the runtime quantile to a sad \(27\%\).

Time Complexity

This solution has linear time complexity, as each node is inspected exactly once.