Happy Friday! It is a typical fall Friday in the Twin Cities of Minneapolis and St. Paul. When I woke up this morning the outside temperature was 38F. The forecasted high for the day is 56F. Tomorrow the forecasted high temperature will be 67F. Will check with my wife if we will grill outside. Not too many grilling days left this year.
Earlier today I read the article Big whales eat 3 times as much as previously thought, which means killing them for food and blubber is even more harmful to the environment by Marianne Guenot. I also read a different article on the same subject titled The Enormous Hole That Whaling Left Behind by Ed Yong. Both articles are in agreement with the research and published papers. As humans, the idea of fertilizing the waters in specific areas seems to be a good thing to do now that the amounts of iron to use have been accurately estimated. Perhaps in the next few decades the oceans will see whales in the numbers they existed 60 years ago.
I continue to attempt solving the set of problems from LeetCode that I have mentioned in several prior posts. Today we will tackle LeetCode 19. Remove Nth Node From End of List which deals with singly linked lists.
If interested in this problem, I suggest that you visit the associated page in the LeetCode website and read the current description of the problem. That done, give it a try before continuing reading this post. It is always better to struggle for no more than ten minutes before looking at a solution.
Given the head of a linked list, remove the nth node from the end of the list and return its head. Constraints: o The number of nodes in the list is sz. o 1 <= sz <= 30 o 0 <= Node.val <= 100 o 1 <= n <= sz Related Topics: o Linked List o Two Pointers
The problem is simple to understand. We are given a linked list and are required to delete the nth element from the end.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
}
}
The signature for the function of interest in Java illustrates that we are given a linked list and a number `n` and we need to return the linked list after the node at position `n` has been removed.
Note that in the comments section the definition for the ListNode class has been provided.
Since we are going to attempt to solve this problem using Java and the VSCode IDE on a Windows machine and not using the on-line IDE provided by LeetCode, we will have to develop a simple test scaffold. The test scaffold will read the input lines, populate the two necessary variables which will be used as arguments for the function of interest, call the function of interest and when done display the modified linked list. Please note that the test scaffold IS NOT PART OF THE SOLUTION.
1,2,3,4,5 2 main <<< arr: [1, 2, 3, 4, 5] main <<< n: 2 main <<< head: 1->2->3->4->5 <<< len: 5 <<< q.val: 3 p.val: 4 main <<< output: 1->2->3->5 1 1 main <<< arr: [1] main <<< n: 1 main <<< head: 1 <<< len: 1 main <<< output: 1,2 1 main <<< arr: [1, 2] main <<< n: 1 main <<< head: 1->2 <<< len: 2 <<< q.val: 1 p.val: 2 main <<< output: 1 1,2,3 3 main <<< arr: [1, 2, 3] main <<< n: 3 main <<< head: 1->2->3 <<< len: 3 main <<< output: 2->3 1,2,3 1 main <<< arr: [1, 2, 3] main <<< n: 1 main <<< head: 1->2->3 <<< len: 3 <<< q.val: 2 p.val: 3 main <<< output: 1->2 1,2,3 2 main <<< arr: [1, 2, 3] main <<< n: 2 main <<< head: 1->2->3 <<< len: 3 <<< q.val: 1 p.val: 2 main <<< output: 1->3
The first two or three test cases were provided by LeetCode. The rest I generated to test some end conditions.
The first input line holds the values for the nodes in the linked list. The second line holds the value for `n` which represents the nth position from the end for the node we need to remove.
Our test scaffold seems to read the first line and put the values into an int[] `arr` array and the `n` value. The values are then displayed to make sure all is well so far.
It appears that a linked list associated with the values in the `arr` array was generated and the nodes were displayed. This was done to make sure all is well prior to calling the function of interest.
While executing the function of interest some values are displayed in order to help us understand the algorithm we used. Please note that such output IS NOT PART OF THE SOLUTION.
The function of interest returns an updated linked list whose contents are then displayed to verify if all went according to our algorithm.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] arr with node values ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read `n` ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< n: " + n);
// **** populate linked list ****
int len = arr.length;
ListNode head = new ListNode(arr[len - 1]);
for (int i = len - 2; i >= 0; i--)
head = new ListNode(arr[i], head);
// ???? ????
System.out.println("main <<< head: " + head.toString());
// **** call function of interest ****
head = removeNthFromEnd(head, n);
// **** display output ****
System.out.print("main <<< output: " + ((head != null) ? head.toString() : ""));
}
We use a buffered reader to read the input lines and populate the `arr` and `n` variables.
We then populate the linked list with the values in the `arr` array.
The function of interest is called and the resulting linked list is displayed.
/**
* Definition for singly-linked list.
*/
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
public String toString() {
// **** initialization ****
ListNode node = this;
StringBuilder sb = new StringBuilder();
// **** traverse the linked list generating the string ****
while (node != null) {
sb.append(node.val);
if (node.next != null)
sb.append("->");
node = node.next;
}
// **** ****
return sb.toString();
}
}
Since we are not using the on-line IDE provided by LeetCode, we also have to implement the ListNode class. Note that we added the `toString()` method to display linked lists. Such addition does not affect the solution which we will discuss next.
/**
* Remove the nth node from the end of the list and return its head.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.9 MB, less than 83.55% of Java online submissions.
*
* Using two pointers.
*
* 208 / 208 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.9 MB
*
* Execution: O(n) - Space: O(1)
*/
static public ListNode removeNthFromEnd(ListNode head, int n) {
// **** initialization ****
ListNode p = null;
ListNode q = null;
int len = 0;
// **** get length of linked list - O(n) ****
for (len = 0, p = head; p != null; p = p.next, len++);
// ???? ????
System.out.println("<<< len: " + len);
// **** remove first element from the linked list (if needed) ****
if (len == n) return head.next;
// **** get to the nth element in the linked list - O(n) ****
int i = 1;
for (q = head, p = head.next; i < len - n; i++) {
p = p.next;
q = q.next;
}
// ???? ????
System.out.println("<<< q.val: " + q.val + " p.val: " + p.val);
// **** remove nth element `p` from the linked list ****
q.next = p.next;
// **** return the head of the updated linked list ****
return head;
}
Our implementation will use two indices (pointers).
We start by declaring and initializing some variables.
We need to get the length of the linked list because the requirements call for removing a node `n` nodes from the end.
We then perform a sanity check. If `n` equals the length of the linked list, we are removing the first node from the linked list, so we do so and return the updated linked list.
Now we need to get to the `n` element from the end. We need to do so starting at the front. Note that we have a second index `q` that follows `p` one node behind. This is done so we can update the `next` element.
We are now ready to remove the nth node which is performed by changing the `next` pointer in the `q` node.
The head of the updated linked list is then returned.
Please take a look at the comment section in the function of interest. The performance information is there.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
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 this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John