Linked List Cycle - LeetCode

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Java Solution 1:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null )
                return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

Java Solution 2:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodeSeen = new HashSet<>();
        while (head != null){
            if(nodeSeen.contains(head))
                return true;
            else
                nodeSeen.add(head);
            head = head.next;
        }
        return false;
    }
}

Palindrome Linked List - LeetCode

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        ListNode prev = new ListNode(head.val);
        ListNode dummy = head;
        while(dummy.next != null){
            ListNode temp = new ListNode(dummy.next.val);
            temp.next = prev;
            prev = temp;
            dummy = dummy.next;
        }
        
        ListNode last = prev;
        ListNode first = head;
        while(first!=null && last!=null){
            if(first.val == last.val){
                first = first.next;
                last = last.next;
            }else{
                return false;
            }
            
        }
        return true;
            
    }
}

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;
    }
}