The Problem:

In this problem, we are given a linked list and a node, this node is not the head of the linked list. In fact, it could be any node, our goal is to delete this node while preserving all the nodes that come before it and the ones that come after it.

Before we begin trying to figure out a solution for this problem, let’s first revisit an important concept, Linked List.

Understanding Linked List:

A linked list is a linear data structure that consists of a sequence of nodes, each containing data and a reference to the next node in the list. It is often used as an alternative to arrays, as it can be more efficient in certain operations such as insertion and deletion.

To understand linked lists, it can be helpful to break it down into 3 parts:

1. Nodes: Each node in a linked list contains some data and a reference to the next node in the list.
2. Head: The head of a linked list is the first node in the list. It is used as the starting point for many operations on the list.
3. Traversal: Traversing a linked list involves starting at the head and following the references from one node to the next until the desired node is reached or the end of the list is reached.

Linked lists can be very useful in solving problems that involve dynamic data structures, as they allow for efficient insertion and deletion of elements. They can also be used in combination with other data structures, such as stacks and queues, to solve more complex problems.

Intuition:

With an understanding of linked lists work, let’s try to break down the problem. We don’t have to worry about making our own linked list data structure as it is given. This is a fairly straightforward problem, Basically we can set the value of head to the next nodes value and then set its link to the next nodes link

This ensures that all the previous node and the nodes that come after head would have their relative order maintained and we also get rid of head.

Summary of Solution

Delete a node from a linked list by setting its value to the value of the next node and updating its next pointer to point to the next node’s next pointer.

Code

This can be translated to code in the following way:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

• Time Complexity O(1)
• Space Complexity O(1)

The time complexity of this solution is O(1) because it only needs to perform a constant number of operations to delete the node.

The space complexity of this solution is also O(1) because it does not use any additional memory.

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!