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.
1 2 3 4 5 6 7 | 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 |
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 headRemove 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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 |
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 headHere, when we should remove the head node, we use the Recursive call to skip it:
1 2 | if head.val == val: return removeNode(head.nextNode, val) |
if head.val == val:
return removeNode(head.nextNode, val)We can also do this iteratively:
1 2 | while head and (head.val == val): head = head.nextNode |
while head and (head.val == val): head = head.nextNode
Both implementation run at O(N) time.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
360 wordsloading...
Last Post: Split a Set into Two with Equal Sums and Distinct Numbers
Next Post: List Calculator Algorithm
