#237

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Delete Node in a Linked List

Delete Node in a Linked List focuses on pointer manipulation to delete a node in a singly linked list without access to the head.

linked list

Problem Statement

In this problem, you're given a singly linked list with nodes having unique values. You are also given a specific node that must be deleted from the list. However, you do not have access to the head of the list. The key task is to remove the node from the list, adjusting the pointers to maintain the list’s integrity.

The node you're given is guaranteed to never be the last node in the list, and you are not allowed to access the head of the list. Instead, you must perform the deletion operation using only the given node's reference.

Examples

Example 1

Input: head = [4,5,1,9], node = 5

Output: [4,1,9]

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]

You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints

The number of the nodes in the given list is in the range [2, 1000].
-1000 <= Node.val <= 1000
The value of each node in the list is unique.
The node to be deleted is in the list and is not a tail node.

Solution Approach

Pointer Manipulation

To delete the given node, you should copy the value from the next node into the current node and then set the current node's next pointer to skip over the next node. This effectively removes the target node from the list.

Constant Time Complexity

This solution works in constant time, O(1), because you are only manipulating pointers and not traversing the list. You only modify the pointers once, ensuring an optimal solution.

No Access to Head

Since you're not given access to the head node, the approach solely relies on adjusting the pointers starting from the given node. This is critical to solving the problem correctly under the given constraints.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

Both the time and space complexities are O(1) because the solution involves pointer manipulation and does not require additional space or list traversal. The deletion operation itself is a constant-time operation.

What Interviewers Usually Probe

Can the candidate explain why this approach works even without accessing the head of the list?
Does the candidate understand the nuances of pointer manipulation and its impact on the linked list?
Is the candidate able to optimize the solution for constant time and space complexities?

Common Pitfalls or Variants

Common pitfalls

Candidates may mistakenly attempt to traverse the list from the head, which is unnecessary since the problem explicitly denies access to the head node.
Not understanding how pointer manipulation works can lead to incorrect handling of the node deletion.
Failing to realize that the given node will never be the tail node might cause confusion about edge cases.

Follow-up variants

What if the given node is at the beginning of the list?
How would the approach change if you had access to the head of the list?
Can the solution be generalized to remove nodes in a doubly linked list?

FAQ

How can I solve Delete Node in a Linked List if I don’t have access to the head?

You solve the problem by manipulating the node’s pointer. Copy the value from the next node into the current one, and adjust the next pointer accordingly to skip the next node.

What is the time complexity of the Delete Node in a Linked List problem?

The time complexity is O(1) because the operation involves a constant number of pointer adjustments.

Can I delete the last node in a singly linked list using this approach?

No, the approach cannot be used for the last node because you do not have access to the node preceding it to adjust its pointer.

What is the main challenge in solving Delete Node in a Linked List?

The main challenge is understanding that pointer manipulation is needed instead of traversing the list, which is a common approach in other linked list problems.

How do I test my solution for Delete Node in a Linked List?

Test the solution by verifying that after deleting the given node, the linked list maintains its integrity, and the result matches the expected list.

terminal

Solution

Solution 1: Node assignment

We can replace the value of the current node with the value of the next node, and then delete the next node. This can achieve the purpose of deleting the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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

Continue Practicing

#234 palindrome linked list #206 reverse linked list #203 remove linked list elements