Delete Node in Linked List

LeetCode Problem #237 (Easy)

Problem Statement

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Note:

The linked list will have at least two elements. All of the nodes' values will be unique. The given node will not be the tail and it will always be a valid node of the linked list. Do not return anything from your function.

Testcases

Example 1:

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 

Example 2:

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.

Prerequisite Knowledge

General Approach

Conventionally, to delete a particular node, we would modify the pointer of the node before the node to be deleted to point to the node after the node to be deleted.

In this example, Node 3 must be deleted. The node before it is Node 2 and the node after it is Node 4. We modify the pointer of Node 2 to point to Node 4. This would cut off the link between Node 2 and Node 3, effectively "deleting" the node from the list.

Source: https://leetcode.com/articles/delete-node-linked-list/

However, we do not have access to the previous node in this problem, so we cannot modify this node to solve the problem.

Algorithm

Swap Nodes Approach

1. Replace the value of the node to be deleted with the value of the node next to it.

2. Set the pointer of the node to be deleted to the node next to its adjacent node.

Copy the value of Node 4 in the place of Node 3

Set the pointer of the copied Node 4 to point to Node 5

Now, we can intuitively apply the approach that was discussed before remove the link to the next node, effectively "deleting" Node 3.

Resultant Linked List

Time Complexity: O(1)

Code

void deleteNode(ListNode* node) {
    // Copy the value of the current node to the next node.
    node->val = node->next->val;

    // Set a pointer from the current node to the node pointed to by the next node
    node->next = node->next->next;
}