How to calculate First Common Ancestor of two Nodes in Binary Tree
First try to understand question. Its a binary tree, not a binary search tree…
September 11, 2019
Given a linked list, remove the n-th node from the end of list and return its head.
There can be many solution for this. Lets start with a brute force simple solution.
You can simply iterate full link list, and count its length. Lets say it: L Calculate L-n. And, move pointer from head to this many times. This node will be the one who has to be deleted.
This requires 2 iteration. Although complexity is still O(n). But, we can think of more optimized version of this algorithm.
We can leverage two pointer concept. Where one pointer moves ahead of first pointer. We just need to keep a distance of ‘n’ between two pointers.
Lets look at the code:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode h = head;
ListNode fast = head;
ListNode prev = null;
for (int i=0; i<n; i++) {
fast = fast.next;
}
while (fast != null) {
prev = h;
h = h.next;
fast = fast.next;
}
if (prev == null) {
//special condition where first pointer is at the head only. And, we want to delete head
return head.next;
}
prev.next = h.next;
return head;
}
Above code does assume that length of list is always greater than equal to ‘n’.
BTW, this code submission to leetcode turns out to be the fastest.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Remove Nth Node From End of List.
First try to understand question. Its a binary tree, not a binary search tree…
Here are some tips while giving your coding interviews. 1. Never try to jump to…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement You are given a string text of words that are placed among…
Problem Statement Write a function that reverses a string. The input string is…
Introduction I will list some of the interesting usage of bitwise operators…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…