Delete Node

Leetcode link: https://leetcode.com/problems/delete-node-in-a-linked-list

Question#

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Implementation#

Since we are only give the node that is to be deleted, we can only delete it by "updating" it. This involves copying the element's value into the current node and repeatedly do this till we reach the 2nd last node and we terminate the linked list there.

def deleteNode(self, node):
# update current node's value with next
curr = node
while(curr.next.next is not None):
curr.val = curr.next.val
curr = curr.next
# we are at the 2nd last node
curr.val = curr.next.val
curr.next = None

Analysis#

  • Time complexity: O(n) where n is the length of the linked list
  • Space complexity: O(1) as no auxillary space is used