Delete Node in a Linked List

Last week I wrote that enormous post about Linked Lists. This week and the next couple of weeks I'd like to do some shorter posts focusing on Linked List problems from LeetCode. These posts will probably make a lot more sense if you read through the Singly Linked List post first, since that will give you a good foundation for the concepts, terminology, and structure that make a Singly Linked List work. The first problem I'll walk through is called Delete Node in a Linked List.

Prompt

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.

Example 1

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.

Example 2

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.

Example 3

Input: head = [1, 2, 3, 4], node = 3

Output: [1, 2, 4]

Example 4

Input: head = [0, 1], node = 0

Output: [1]

Example 5

Input: head = [-3, 5, -99], node = -3

Output: [5, -99]

Stating the Problem in My Own Words

I need to write a function named deleteNode that accepts a node from a Linked List as its only parameter. This function doesn't return anything, and instead just "removes" the node from the Linked List.

The node we are "removing" will not be the Linked List's tail node, which serves as a bit of a hint for the approach — node will have some value in its next pointer.

It's worth noting that LeetCode does their Linked Lists a little bit differently than what I implemented in my Singly Linked List blog post. They don't track the tail or the length. But those don't really matter for this problem.

Approach

I have "removes" in quotes above because this isn't a true deletion operation. Instead, we are just going to replace the node's value (val) with the val of the next node in the list, and then set node's next pointer to equal the next node's next.

function deleteNode(node) {  node.val = node.next.val;  node.next = node.next.next;}

This code doesn't return anything, and it simply reassigns val and next to be those of the next node in the Linked List.

So for our first example, the whole list is head = [4, 5, 1, 9], and the given node is 5.

head:  - val: 4  - next:    - val: 5    - next:      - val: 1      - next:        - val: 9        - next: null

The above function accepts 5 as its node, including 5's next pointer, which references 1, whose next pointer references 9.

The function reassigns 5's value, val to be 1, and its next pointer to refer to 9. In effect, the list becomes:

head:  - val: 4  - next:    - val: 1    - next:      - val: 9      - next: null

This gives us the [4, 1, 9] result we are looking for. This works for all of the examples listed above, and anywhere where we are "deleting" anything except the tail node.

Solution

function deleteNode(node) {  node.val = node.next.val;  node.next = node.next.next;}

Big O of this Solution and Further Optimization

We aren't doing any list traversal or anything, just two reassignment operations no matter what node we're given, so this little solution works in constant time, O(1).

There is one last thing I'd like to point out in the way of further optimizing this solution. I pointed out above that this isn't a true deletion operation, it's mostly just sliding val and next up one node. I would much prefer to find the node before the node we plan to delete, then set its next to be the node after the deleted node, and then set the deleted node's next to null. It's a subtle difference, but this last operation would help us ensure there is no false head leading into the list. Even if that de-coupled node still existed in memory, its next would not point back into the linked list.