31
LinkedList Questions: Delete a given node in constant time
In this series of posts, I will discuss coding questions on the
The posts in this series will be organized in the following way,
LinkedList
Data structure. The posts in this series will be organized in the following way,
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.
π‘ Give yourself atleast 5 mins to figure out the solution :)

It is a warm-up question, there's not much to explain,
//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) {}
};
#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;
}
};
No iteration or recursion is done.
No extra space is used.
31