Remove all elements from a linked list of integers that have value val.
Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5
- the regular case is simple.
e.g. to delete 6 below, we can use a node(delnode) to store 6’s next node
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
Below is the white board:
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
- Time complexity is O(n)
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