Delete Node in a Linked List Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Cisco Facebook Goldman Sachs Google Microsoft Qualcomm SamsungViews 3859

Problem Statement :

Delete Node in a Linked List Leetcode Solution – 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 :

Example 1

Delete Node in a Linked List Leetcode Solution

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

Delete Node in a Linked List Leetcode Solution

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.

Constraints :

Explanation :

  • Given a node, not the head of the Linked List.
  • Without accessing the head of the list we need to delete the given node.
  • In the constraint, the given node can’t be the tail of the List.

Observation :

  • This problem was can be easily solved in linear time if we had the head of the list but we only have the node, not the head so we cannot iterate through the list.
  • Iteration is restricted so, we need to do something in place.
  • It is also given, that the node can’t be the tail of the list.
  • If we observe, then we can’t delete the given node, because deleting a node required the reference of the previous node.

Approach :

  • From the above observation, deleting the given node is not possible, but we can delete the next node.
  • If we need to delete the next node then our current node will become the previous node of the next node.
  • At first, copy the value of the next node in the given node.

                                            node.val=node.next.val;

  • Now, store the next node for our future reference.

                                                    ListNode next= node.next.next;

  • Make the given node, as the previous node.

                                                 ListNode prev =node;

  • Now, delete the next node of the previous node.

                                                          prev.next=next;

Code for Delete Node in a Linked List :

Java  Code  for Delete Node in a Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        ListNode next= node.next.next;
        ListNode prev =node;
        prev.next=next;
    }
}

C++ Code  for Delete Node in a Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
            node->val=node->next->val;
        ListNode* next= node->next->next;
        ListNode* prev =node;
        prev->next=next;
    }
};

Complexity Analysis of Delete Node in a Linked List Leetcode Solution

Time Complexity

O(1), constant time.

Space Complexity 

O(1), constant space.

Translate »