Teaching Kids Programming – Algorithms to Remove Nodes from a Linked List

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Linked List, remove the nodes with a given value.

Remove a Node using Recursion

If the head is to remove, we need to abandon it by moving the head to next. This can be done recursively.

def removeNode(head, val):
    if head is None:
        return None
    if head.val == val:
        return removeNode(head.nextNode, val)
    head.nextNode = removeNode(head.nextNode, val)
    return head

Remove a Node using Iterative Algorithm

We can also do this iteratively. In order to do so, we need to keep previous and current node, then when current node is to remove, we re-link the previous node to current’s next node.

def removeNode(head, val):
    if head is None:
        return None
    if head.val == val:
        return removeNode(head.nextNode, val)
    prev = head
    cur = head.nextNode
    while cur:
        while cur is not None and cur.val == val:
            prev.nextNode = cur.nextNode
            cur = cur.nextNode
        if cur is None:
            break
        prev, cur = cur, cur.nextNode
    return head

Here, when we should remove the head node, we use the Recursive call to skip it:

    if head.val == val:
        return removeNode(head.nextNode, val)

We can also do this iteratively:

while head and (head.val == val):
   head = head.nextNode

Both implementation run at O(N) time.

–EOF (The Ultimate Computing & Technology Blog) —