Delete Node From Linked List Editorial

Practice Problem Link: Delete Node From Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Delete a given node from a singly-linked list. You do not have access to the head of the list. Also, the node to be deleted is not the tail of the linked list.

Approach

Since we do not have access to the head of the list, traversing the list is not an option. All we need to do is change the data and pointer of the current node with that of the next node.

Analysis

• Time Complexity: O(1)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

void deleteNode(ListNode* node) {
    ListNode *nextNode = node->next;
	node->data = nextNode->data;
	node->next = nextNode->next;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/

class Solution {
	void deleteNode(ListNode node) {
	    ListNode nextNode = node.next;
		node.data = nextNode.data;
		node.next = nextNode.next;
	}
}