algoadvance

Leetcode 237. Delete Node in a Linked List

Problem Statement:

You are given a node in a linked list (not the tail node). Write a method to delete this node.

The node is guaranteed not to be the last node and will always be a valid node of the linked list.

You will not be given access to the head of the linked list, instead you will be given access to the node to be deleted directly.

Let’s look at the function signature:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public void deleteNode(ListNode node) {
    // your code here
}

Clarifying Questions:

  1. Is the node guaranteed not to be null?
    • Yes, the problem guarantees a valid node which is not the tail node.
  2. Can the values in the linked list be non-unique?
    • Yes, the values can be non-unique.

Strategy:

  1. Overwrite the Current Node:
    • Since we don’t have access to the node before the current node, we can’t update its next pointer.
    • Instead, we can copy the value of the next node to the current node and then bypass the next node.
  2. Implementation Steps:
    • Set the current node’s value to the value of the next node.
    • Point the next pointer of the current node to the node after the next node.

Code:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public void deleteNode(ListNode node) {
    // Given node is not the tail and is always valid
    // Copy the next node's value to the current node
    node.val = node.next.val;
    // Bypass the next node
    node.next = node.next.next;
}

Time Complexity:

Explanation:

By copying the value from the next node to the current node and bypassing the next node, we effectively delete the current node without needing access to the head of the list. This is efficient and meets the constraints of the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI