DEV Community

loading...
Cover image for LinkedList Questions: Delete a given node in constant time

LinkedList Questions: Delete a given node in constant time

Kathan Vakharia
DS-Algo Tenderfoot | Computer Scientist | Aspiring Gopher | DataScience Enthusiast | Python & C++ ๐Ÿ’•
ใƒป2 min read

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,

  1. Question Link โ“
  2. Possible Explanation ๐Ÿ“
  3. Documented C++ Code ๐Ÿงน
  4. Time and Space Complexity Analysis โŒ›๐ŸŒŒ

The Question

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.

https://leetcode.com/problems/delete-node-in-a-linked-list/

๐Ÿ’ก Give yourself atleast 5 mins to figure out the solution :)

Explanation

image

It is a warm-up question, there's not much to explain,

  1. Copy the data of the next node into the given node.
  2. Make the given node point to the next's neighbor.
  3. Free up the old neighbor of the given node.

C++ Code

Definition of LinkedList

//Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Enter fullscreen mode Exit fullscreen mode

Solution

#include <bits/stdc++.h>
#include "../linkedlist.h"
using namespace std;

/*
-Time:O(1)
-Space:O(1)
*/
class Solution
{
public:
    //! given node isn't the "tail" node
    void deleteNode(ListNode *node)
    {
        ListNode *temp = node->next;

        //I can do this only because node isn't the tail node
        //and "node->next" will not null therefore
        node->val = node->next->val;
        node->next = node->next->next;

        delete temp;
    }
};

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Time Complexity: O(1)

No iteration or recursion is done.

Space Complexity: O(1)

No extra space is used.

Discussion (0)