I noticed that a second implementation of the function of interest was missing from this post. I have updated the GitHub repo and the post. Sorry about that!
In this post we will solve the LeetCode 237 Delete Node in a Linked List problem using the Java programming language and the VSCode IDE on a Windows platform. Java is quite portable so it should run on most (never generalize) platforms.
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. Constraints: o The number of the nodes in the given list is in the range [2, 1000]. o -1000 <= Node.val <= 1000 o The value of each node in the list is unique. o The node to be deleted is in the list and is not a tail node
The problem at first glance seems to be simple. We have to delete a node from a singly linked list. The complication arises when we are only given the node to delete. In general, to delete a node from a linked list we are given the head of the 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) {
}
}
The signature for the function of interest is as expected. We are just given the node that we should delete from the list. In addition we are provided in the comment section the definition for the TreeNode class.
I will be solving this problem on my Windows computer. I will not be using the online IDE provided by LeetCode. When I am satisfied with the code I am locally developing I will just copy and paste it into the online IDE and will test and submit it for evaluation.
Due to the approach I am using, I will need to generate a test scaffold. Please note that the test code IS NOT PART OF THE SOLUTION!
4,5,1,9 5 main <<< arr: [4, 5, 1, 9] main <<< v: 5 main <<< head: 4->5->1->9 main <<< node: 5 main <<< output: 4->1->9 1,2,3,4 3 main <<< arr: [1, 2, 3, 4] main <<< v: 3 main <<< head: 1->2->3->4 main <<< node: 3 main <<< output: 1->2->4 0,1 0 main <<< arr: [0, 1] main <<< v: 0 main <<< head: 0->1 main <<< node: 0 main <<< output: 1 -3,5,-99 -3 main <<< arr: [-3, 5, -99] main <<< v: -3 main <<< head: -3->5->-99 main <<< node: -3 main <<< output: 5->-99 1,99,2,3,4,5,6,7,8,9 99 main <<< arr: [1, 99, 2, 3, 4, 5, 6, 7, 8, 9] main <<< v: 99 main <<< head: 1->99->2->3->4->5->6->7->8->9 main <<< node: 99 main <<< output: 1->2->3->4->5->6->7->8->9 1,2,3,4,5,6,7,8,99,9 99 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 99, 9] main <<< v: 99 main <<< head: 1->2->3->4->5->6->7->8->99->9 main <<< node: 99 main <<< output: 1->2->3->4->5->6->7->8->9
Each test case is separated from others by double blank lines.
The first two lines of each test case are input lines. The first holds the values for the nodes in the linked list. The second holds the value for the node that needs to be deleted from the linked list.
The rest of the lines are used to make sure things are working as expected.
/**
* Test scaffold.
* !!! NOT PART OF THE SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read node values ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read value for node to be deleted ****
int v = Integer.parseInt(br.readLine().trim());
// **** ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< v: " + v);
// **** ****
ListNode head = null;
ListNode tail = null;
ListNode node = null;
// **** populate linked list ****
for (int val : arr) {
// **** create new node ****
ListNode n = new ListNode(val);
// **** add node to linked list ****
if (head == null) {
head = n;
tail = n;
} else {
tail.next = n;
tail = n;
}
// **** remember this node ****
if (val == v) node = n;
}
// ???? ????
System.out.print("main <<< head: ");
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
if (p.next != null) System.out.print("->");
}
System.out.println();
System.out.println("main <<< node: " + node.val);
// **** call the function of interest ****
deleteNode(node);
// **** display output ****
System.out.print("main <<< output: ");
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
if (p.next != null) System.out.print("->");
}
System.out.println();
}
Our test code reads the two input lines and creates and populates an array with the values for the nodes in the linked list and the value for the node we have to delete. The values are displayed in order to make sure all is well so far.
We then declare three additional variables. The `head` will be for the head of our linked list. The `tail` refers to the tail element in the linked list, and `node` will hold the reference to the node we will delete from the linked list. This will serve as the argument that our test scaffold will pass to the function of interest.
We then enter a loop that populates the linked list. Note that in addition we generate a reference to such an object in the `node` variable.
Our test code then displays the value for the node of interest and the contents of the linked list. This is done in order to make sure things are working well so far.
The function of interest is then called. After the function returns, the original linked list should no longer hold the node that was deleted. To verify this our test scaffold displays the contents of the linked list.
I could have refactored the code that is used to display the linked list into a function. In production code that would be a must. In this case I will leave it as is.
/*
* Definition for singly-linked list.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
@Override
public String toString() {
return "" + this.val;
}
}
Since I am developing the solution on my Windows computer, I will have to implement the ListNode class. If you solve the problem using the online IDE provided by LeetCode, you will not have to implement this class. The class implementation IS NOT PART OF THE SOLUTION!
/**
* Delete this node from a singly-linked list.
*
* Execution: O(n) - Space: O(1)
*
* 41 / 41 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.3 MB
*/
static public void deleteNode0(ListNode node) {
// **** initialization ****
ListNode p = node;
// **** traverse the linked list - O(n) ****
while (p != null) {
// **** copy value from next node ****
p.val = p.next.val;
// **** terminate linked list ****
if (p.next.next == null) p.next = null;
// **** move to next node ****
p = p.next;
}
}
The idea is to copy into the node that has to be deleted the contents of the next node. The process repeats until we reach the node before the tail. Such a node needs to be deleted. This is why the node to be deleted will not be the tail (check the constraints for this problem).
We create a reference / pointer `p` used to traverse the linked list starting with the node that needs to be deleted.
We enter a while loop. In the loop we start by copying the value from the next node to the current node. We check if the following (next) node is the tail of the linked list. If so we set the next node in the current node to null. We then update the value for `p` to continue traversing the linked list.
/**
* Delete this node from a singly-linked list.
*
* Execution: O(1) - Space: O(1)
*
* 41 / 41 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.6 MB
*/
static public void deleteNode(ListNode node) {
// **** copy value from next node ****
node.val = node.next.val;
// **** remove the next node in the linked list ****
node.next = node.next.next;
}
This is the second implementation of the function of interest. As you can see we copy the value of the next node and just delete the next node from the linked list. This function runs in O(1) execution order and in O(1) space.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named DeleteNodeInLinkedList.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John