Remove Nth Node From End of List - LeetCode

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null)
            return head;
        ListNode dummy = head;
        ListNode first = new ListNode(0);
        first.next = head;
        int size = 0;
        while (dummy != null){
            size++;
            dummy = dummy.next;
        }
        int k = size-n;
        if(k < 0)
            return null;
        dummy = first;
        while(k > 0){
            dummy = dummy.next;
            k--;
        }
        
        dummy.next = dummy.next.next;
        
        return first.next;   
    }
}

Delete Node in a Linked List - LeetCode

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

Given linked list -- head = [4,5,1,9], which looks like following:

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 after calling your function.

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 after calling your function.

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.

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Longest Common Prefix - LeetCode

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Java Solution :

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        String prefix = strs[0];
        for(int i =1 ; i < strs.length ; i++){
            while(strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0,prefix.length()-1);
                if(prefix.isEmpty())
                    return "";
            }
        }
        return prefix;
    }
}

Valid Palindrome - LeetCode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Java Solution :

class Solution {
    public boolean isPalindrome(String s) {
         if(s.length() == 0 || s == null)
             return true;
        int i =0;
        int j = s.length()-1;
        
        while(i < j){
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }
            if(i<j && Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
                return false;
        }
    return true;
    }
}

Plus One - LeetCode

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Java Solution :

class Solution {
    public int[] plusOne(int[] digits) {
        int lastIndex = digits.length-1;
        int carry = 1;
        int[] plusOne = new int[digits.length+1];
        if(digits[lastIndex]<9){
            digits[lastIndex]=digits[lastIndex]+1;
            return digits;
        }else{
            for(int i=digits.length-1;i>=0;i--){
                if(digits[i]==9){
                 digits[i]= (digits[i]+carry);
                 carry = digits[i]/10;
                 digits[i]=digits[i]%10;   
                }
                else{
                    digits[i]=digits[i]+carry; 
                    carry = 0;
            }
            }
            if(carry == 1){
                plusOne[0] = 1;
                for(int i=0;i<digits.length;i++){
                    plusOne[i+1] = digits[i];
                }
                return plusOne;
            }
        }
        return digits;
    }
}

Valid Anagram - LeetCode

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Java Solution :

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;
        int[] tableA = new int[26];
        
        for(int i =0 ; i < s.length() ; i++){
            tableA[s.charAt(i)-'a']++;
        }
        
        for(int i=0;i<t.length(); i++){
            tableA[t.charAt(i)-'a']--;
            if(tableA[t.charAt(i)-'a'] < 0)
                return false;
        }
        return true;
    }
}

Reverse String -LeetCode

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Java Solution :

class Solution {
    public void reverseString(char[] s) {
        if(s.length == 0 || s == null)
            return;
        int k = s.length;
        for(int i =0 ; i < k/2;i++){
            char temp = s[i];
            s[i] = s[k-i-1];
            s[k-i-1] = temp;
        }
    }
}