Intersection of Two Linked Lists - LeetCode

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1)

• Java Solution:

• /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) {
   *         val = x;
   *         next = null;
   *     }
   * }
   */
  public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          ListNode p = headA;
          ListNode q = headB;
          int lenA = 0;
          int lenB = 0;
          while(p!=null){
              lenA++;
              p = p.next;
          }
          while(q!=null){
              lenB++;
              q=q.next;
          }
          p = headA;
          q= headB;
          
          if(lenA > lenB){
              int diff = lenA-lenB;
              for(int i=0;i<diff;i++)
                  p = p.next;
          }else if(lenA < lenB){
              int diff = lenB-lenA;
              for(int i=0;i<diff;i++)
                  q = q.next;
          }
          
          while (p!=null && q!=null){
              if(p.val == q.val)
                  return p;
              p = p.next;
              q = q.next;
          }
          return null;
      }
  }

Add Two Numbers - LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
    }
}

Two Sum II - Input array is sorted - LeetCode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Java Solution :

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0; i < numbers.length ; i++){
            if(map.containsKey(target-numbers[i]) && i!=map.get(target-numbers[i])){
                return new int [] {map.get(target-numbers[i])+1,i+1};
            }else{
                map.put(numbers[i],i);
            }
        }
        return null;
    }
}

Best Time to Buy and Sell Stock || -LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Java Solution:

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit =0;
        for(int i=1 ; i < prices.length; i++){
            if(prices[i]>prices[i-1])
                maxProfit+=prices[i]-prices[i-1];
        }
        return maxProfit;
    }
}

Move Zeros - LeetCode

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Java Solution :

class Solution {
    public void moveZeroes(int[] nums) {
        int j =0;
        for(int i =0; i < nums.length ; i++){
             if(nums[i] !=0){
                 nums[j] = nums[i];
                 j++;
             }
            }
        while(j < nums.length){
            nums[j++]=0;
        }
        
        }
    }

Intersection of Two Arrays II-LeetCode

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Java Solution :

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
  HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

  for(int i : nums1){
   if(!map.containsKey(i)){
    map.put(i,1); 
   }else{
    map.put(i,map.get(i)+1);
   }
  }
  ArrayList<Integer> list = new ArrayList<Integer>();

  for(int j : nums2){
   if(map.containsKey(j)){
    if(map.get(j)>=1){
     list.add(j);
     map.put(j,(map.get(j))-1);

    }
   }
  }

  int[] common = new int[list.size()];
  int j =0;

  for(int k:list){
   common[j]=k;
   j++;

  }
  return common;
 }
}

Single Number - LeetCode

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Java Solution: Using HashSet

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i : nums)
        {
            if(!set.add(i))
                set.remove(i);
        }
        Iterator<Integer> it = set.iterator();
        return it.next();
        
    }
}

Java Solution : Using XOR Operation

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int x =0;
        for(int n : nums){
            x = x ^ n;
        }
        return x;
    }
}