Merge k sorted arrays

Problem

Given k sorted arrays of size n each, merge them and print the sorted output.

Solutions

This problem can be solved in multiple ways.

- Take first two arrays and merge those. Now the rest all arrays with the merge result one by one.

- We can use the min heap of size 'k'. Add one element from each array and remove smaller element from heap. Once the smaller element is removed, from the same array insert next element in to heap. This way remove all the elements from heap and put in to merge array.

- Lastly instead of maintaining heap, we can just compare one element from each array, compare min from those and add to merge result. Now take next element from same array. Follow this till all elements are sorted. Solution below implements this approach.

import java.util.ArrayList;
import java.util.List;

public class MergeKSortedArrays {
    public static void MergeSortedArrays(int[][] sortedArrays) {
        int maxSize = sortedArrays.length * sortedArrays[0].length;

        int[] mergedArray = new int[maxSize];

        List arrayIndices =  new ArrayList<>();
        for (int[] sortedArray : sortedArrays) arrayIndices.add(0);

        for (int i = 0; i < maxSize; i++){
            int minSoFar = Integer.MAX_VALUE;
            int minIndex = 0;

            for(int index = 0; index < arrayIndices.size(); index++){
                if ( sortedArrays[index].length > arrayIndices.get(index) && sortedArrays[index][arrayIndices.get(index)] < minSoFar){
                    minSoFar = sortedArrays[index][arrayIndices.get(index)];
                    minIndex = index;
                }
            }
            mergedArray[i] = sortedArrays[minIndex][arrayIndices.get(minIndex)];
            arrayIndices.set(minIndex, arrayIndices.get(minIndex) + 1);
        }

        System.out.println("Merged : ");
        for (int i : mergedArray){
            System.out.print( i + ", ");
        }
    }

    public static void main(String[] args) {

        int[][] A = new int[5][];

        A[0] = new int[] { 1, 5, 8, 9 };
        A[1] = new int[] { 2, 3, 7, 10 };
        A[2] = new int[] { 4, 6, 11, 15 };
        A[3] = new int[] { 9, 14, 16, 19 };
        A[4] = new int[] { 2, 4, 6, 9 };

        MergeSortedArrays(A);
    }
}

Comments are welcome.

Buildings which can see the sun

Problem

An array of integers is given which represents the heights of n buildings.Sun start falling from the left side. If there is a building of certain Height, all the buildings right of it having lesser heights cannot see the sun. Find the no. of buildings which can see the sun.

Solutions

Starting from we have to find the building which has same or bigger height than building on left side. Which means we have to list out local maximum in the array, which will give us the building which can see the sun.
Solution below uses an temp list for storing the local maximum so far.

import java.util.ArrayList;
import java.util.List;

public class SunViewBuilding {

    public static int GetSunViewCount(int[] buildingHeights){
        if (buildingHeights.length <= 0)
            return 0;

        List localMax = new ArrayList<>();

        localMax.add(buildingHeights[0]);
        for (int i =1;  i < buildingHeights.length; i++){
            if (localMax.get(localMax.size()-1) <= buildingHeights[i]){
                localMax.add(buildingHeights[i]);
            }
        }

        return localMax.size();
    }

    public static void main(String[] args) {
        int[] input = {12, 11, 13, 5, 30, 6, 30};
        System.out.println("Buildings which can see the sun : " + GetSunViewCount(input));
    }
}

Comments are welcome. Question source geeksforgeeks

Swap two Strings without using third user defined variable

Problem

Given two string variables a and b, swap these variables without using temporary or third variable in Java. Use of library methods is allowed.

Solutions

We can use the String Split method and a separator to separating two string. We can also do this by using the substring method. Code below implement both the solutions.

 
public class SwapWithoutVar {
    public static void main(String[] args) {
        String a = "Hello";
        String b = "World";

        //Using String Split
        SwapWithSplit(a, b);

        //Using String Substring
        SwapWithSubString(a, b);

    }

    private static void SwapWithSubString(String a, String b) {
        System.out.println(String.format("Before Swap : a - %s, b - %s", a, b));
        b = a + b;
        a = b.substring( b.indexOf(a) + a.length());
        b = b.substring(0, b.indexOf(a));
        System.out.println(String.format("After Swap : a - %s, b - %s", a, b));
    }

    private static void SwapWithSplit(String a, String b) {
        System.out.println(String.format("Before Swap : a - %s, b - %s", a, b));
        b = b + "," + a;
        a = b;
        b = b.split(",")[1];
        a = a.split(",")[0];
        System.out.println(String.format("After Swap : a - %s, b - %s", a, b));
    }
}

Comments are welcome. Question source geeksforgeeks

Sorted subsequence of size n

Problem

Given an array, the task is to find n elements of this array such that they are in sorted form. Eg. For n =3 any three elements a[i], a[j] and a[k], they follow this relationship : a[i] < a[j] < a[k].

Solutions

If we have to find out the sorted sub-sequence means we need elements in incrementing order. Let's assume first element from array is less than second then we can add both elements in temp storage, if any element is less than element inserted in temp storage add this to another temp storage as new solution. We can follow this method will we get required number of elements in sorted order.
The solution below implement this approach using stack as temp storage. This solution finds out all the sorted subsequence in the array. The complexity of this solution is o(n) as we are going over all the elements not more than once. 

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class SortedSubSeq {

    public static List getSortedSubSequence(int[] input, int n){
        List> seqList = new ArrayList>();
        boolean added= false;
        for (int i : input){
            for (Stack s : seqList) {
                if (!s.empty() && s.peek() < i) {
                    s.push(i);
                    added = true;
                }
            }

            if (!added){
                Stack newSubSequence = new Stack<>();
                newSubSequence.push(i);
                seqList.add(newSubSequence);
            }
            added = false;
        }

        for (Stack s : seqList) {
            if (s.size() >= n) {
                List result = new ArrayList<>();
                result.addAll(s);
                return result;
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int[] input = {12, 11, 10, 5, 7, 6, 30};

        List result = getSortedSubSequence(input, 3);
        System.out.println("Sorted subsequence of length 3 : ");
        for (Integer i : result){
            System.out.print(i + " ");
        }
    }

}

Comments are welcome. Question source geeksforgeeks

Longest consecutive sequence in Binary tree

Problem

Given a binary tree, we need to find length of the longest consecutive sequence path where path refers to sequence of node in tree along with parent child connection.

Solutions

We can solve this in two parts, one will find out the root to leaf path and second will check the longest sequence in that path. Root to leaf can be found by traversing tree using pre-order traversal. This way we can find out the longest sequence in binary tree. 

Solution below implements the approach.

import java.util.ArrayList;
import java.util.List;

public class LongestSeqInBT {
    private  List rootToLeafPath;
    private List longestSeq;

    public LongestSeqInBT(){
        rootToLeafPath = new ArrayList<>();
        longestSeq     = new ArrayList<>();
    }

    public void longestSeqInBTree(Node bTreeRoot, int index){
        if (bTreeRoot != null){
            if(rootToLeafPath.size() > index){
                rootToLeafPath.set(index, bTreeRoot.data);
            }
            else
                rootToLeafPath.add(bTreeRoot.data);

            longestSeqInBTree(bTreeRoot.left, index + 1);
            longestSeqInBTree(bTreeRoot.right, index + 1);
        }
        else {
            LongestSeqInList(index);
        }
    }

    private void LongestSeqInList(int index) {

        if (index <= 0)
            return;

        Integer prev = Integer.MAX_VALUE;
        Integer maxSeqSize = 1;
        Integer currentSeqSize = 1;
        Integer startIndex = -1;
        Integer counter = 0;
        for (Integer i : rootToLeafPath){
            counter++;
            if (i - 1 == prev){
                currentSeqSize++;
                if (currentSeqSize > maxSeqSize){
                    maxSeqSize = currentSeqSize;
                    startIndex = counter - currentSeqSize;
                }
            }
            else
                currentSeqSize = 1;
            prev = i;
        }

        if (maxSeqSize > longestSeq.size() && startIndex > -1){
            longestSeq.clear();
            for (int i = startIndex; i < startIndex + maxSeqSize ; i++) {
                longestSeq.add(rootToLeafPath.get(i));
            }
        }
    }
 
    public static void main(String[] args) {

        LongestSeqInBT btSeq = new LongestSeqInBT();

        Node node3 = new Node(3);
        Node node2 = new Node(2, node3, null);

        Node node7 = new Node(7);
        Node node6 = new Node(6, node7, null);
        Node node5 = new Node(5);
        Node node4 = new Node(4, node5, node6);

        Node bTree = new Node(1, node4, node2);

        Node.PrintInOrder(bTree);

        System.out.println("");
        btSeq.longestSeqInBTree(bTree, 0);
        for (Integer i : btSeq.longestSeq){
            System.out.print(i + " ");
        }
    } 
}

Comments are welcome. Question source geeksforgeeks

Rearrange array such that all odd numbers occupy odd positions

Problem:
Rearrange array such that all odd numbers occupy odd positions and even numbers occupy even position. Order of numbers needs to be maintained without use of extra space.

Solution:
For maintaining the number order, you can apply movement. if odd or even is not in place then find next required number and move other numbers to right. Solution below implements this.

 
public class OddEven {

    public static void main(String[] args) {

        int[] input = {1, 23, 4, 6, 2 , 3, 7, 12, 15, 16, 19, 100};

        System.out.println("Before : ");
        for (int i : input){
            System.out.print(i + " ");
        }

        oddEvenWithoutBuffer(input);

        System.out.println("\nAfter : ");
        for (int i : input){
            System.out.print(i + " ");
        }
    }

    static void oddEvenWithoutBuffer(int[] input) {

        for (int i = 0; i < input.length; i++) {

            int j = i + 1;
            if (i % 2 == 0) {
                if (input[i] % 2 != 0) {
                    while (j < input.length && input[j] % 2 != 0)
                        j++;
                } else continue;
            } else {
                if (input[i] % 2 == 0) {
                    while (j < input.length && input[j] % 2 == 0)
                        j++;
                } else continue;
            }

            if (j < input.length) {
                int temp = input[j];
                for (int m = j; m > i; m--) input[m] = input[m - 1];
                input[i] = temp;
                i++;    //Skip next as its in place, due to movement
            } else
                break;      //No more even or odd remaining.
        }
    }
}

Comments are welcome. Question source geeksforgeeks

Maximum sum such that no two elements are adjacent

Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Solution

Simplest solution is to sum all the elements in the array, which are not adjacent and find out max sum. But this solution is not efficient. 

We can device this problem in smaller problem, like if we find out for a sub set of array the max sum once we can re-use this sum. 

Solution below implements both the approaches, one with all permutations and second using dynamic programing.

  
public class MaxSumWithoutAdjecent {
    private int[] dp;

    public MaxSumWithoutAdjecent(int size){
        setInputSize(size);
    }

    public void setInputSize(int size){
        dp = new int[size +1];
        for (int i=0; i < dp.length; i++)
            dp[i] = -1;
    }

    public int maxSumByDp(int[] array, int index){
        if (index >= array.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];

        int max = Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
        dp[index] = max;
        return max;
    }

    public static void main(String[] args) {
        int[] array = {5,  5, 10, 40, 50, 35};

        MaxSumWithoutAdjecent maxsummer = new MaxSumWithoutAdjecent(array.length);

        System.out.println(maxSum(array, 0));
        System.out.println(maxsummer.maxSumByDp(array, 0));

        int[] array1 = {3, 2, 5, 10, 7};
        maxsummer.setInputSize(array1.length);
        System.out.println(maxSum(array1, 0));
        System.out.println(maxsummer.maxSumByDp(array1, 0));
    }

    public static int maxSum(int[] array, int index){
        if (index >= array.length)
            return 0;
        return Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
    }
}

Comments are welcome. Question source geeksforgeeks

Next greater number with same digits

Given an integer number, find out next greater number formed with same digits.

Approach 1: 
If we carefully look at integer numbers, if all the digits are sorted in ascending order then it's the lowest number you can get with same digits. If we descending sort all the numbers then we will get the greatest number which can be formed with same digits.
So in order to generate the required number start from rightmost digit, check where any of the digits is less than the digit in right, if yes then mark that position.
Now sort all the digits in right from that position, and replace that digit with a greater digit in the sorted list.

The solution below implements this approach.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NextNumberWithSameDigits {
    public static void main(String[] args) {
        int number = 12;

        List integerList = ConvertToArray(number);
        int swapIndex = 1;
        while (swapIndex < integerList.size() && integerList.get(swapIndex-1) <= integerList.get(swapIndex)){
            swapIndex++;
        }

        if (swapIndex == integerList.size()){
            System.out.println("No next greater number can be formed");
            return;
        }

        Integer value = integerList.get(swapIndex);

        List copyList = integerList.subList(0, swapIndex+1);
        Collections.sort(copyList);

        int replaceIndex = 0;
        for (; replaceIndex < copyList.size(); replaceIndex++){
            if (value.equals(copyList.get(replaceIndex))){
                break;
            }
        }

        //If digits are duplicate in the list then we should need next greater digit
        for (; replaceIndex + 1 < copyList.size(); replaceIndex++){
            if (!copyList.get(replaceIndex).equals( copyList.get(replaceIndex+1))){
                Integer temp = copyList.get(replaceIndex+1);
                copyList.remove(replaceIndex+1);
                copyList.add(0, temp);
                break;
            }
        }

        Collections.reverse(copyList);
        Collections.reverse(integerList);

        StringBuilder str = new StringBuilder();
        integerList.forEach(str::append);

        System.out.println("Number : " + number);
        System.out.println("Next   : " + str.toString());

    }

    public static List ConvertToArray(int num){
        List integerList = new ArrayList<>();
        while (num > 0){
            int reminder = num %10;
            num = num/10;
            integerList.add(reminder);
        }
        return integerList;
    }
}

Comments are welcome.

Finding out running Maximum element from stack

You have an empty sequence, and you will be given  queries. Each query is one of these three types:

• 1 num  Push the element x into the stack.
• 2          Delete the element present at the top of the stack.
• 3          Print the maximum element in the stack.

For each query of type 3 return the max element from the current stack.
Input:

10
1 9
1 7
3 
2
1 20
1 26
2
3
1 45
3

 Output: 

9
20
45 

Approach 1:
Use a temp variable to store a maximum element. When the maximum is removed from the stack, iterate through stack and find out next maximum element.

Approach 2:
When we are removing any element from stack and if its max element, then we will have to re-calculate the maximum from existing stack which would be time consuming task. 
We can use the another stack to store the local maximum for stack so far, by adding element in local maximum stack if its greater than current top element.
Only overhead with the maximum stack is when any of the max is removed from the original stack, we should also remove it from maximum stack.
Code below implement this solution.

import java.util.Scanner;
import java.util.Stack;

public class MaxStack {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int queries = scanner.nextInt();

        Stack integerStack = new Stack();
        Stack localMaxStack = new Stack();

        while (queries > 0) {
            int query = scanner.nextInt();
            queries--;
            switch (query) {
                case 1:
                    int value = scanner.nextInt();
                    integerStack.push(value);
                    if (localMaxStack.isEmpty() || value >= localMaxStack.peek())
                        localMaxStack.push(value);
                    break;
                case 2:
                    if (integerStack.isEmpty()) {
                        System.out.println("Invalid Operation !! Stack Empty");
                        System.exit(-1);
                    }
                    value = integerStack.pop();
                    if (!localMaxStack.isEmpty() && value == localMaxStack.peek())
                        localMaxStack.pop();
                    break;
                case 3:
                    if (!localMaxStack.isEmpty()) {
                        System.out.println(localMaxStack.peek());
                    }else {
                        System.out.println("Stack Empty");
                    }
                    break;
                default:
                    System.out.println("Invalid Operation");
                    System.exit(-1);
            }
        }
    }
}

Comments are welcome.

Left shift or Rotating an Array

Given an array and a number, rotate the array to the left by given number positions i.e; shift the array elements to the left.

Example: The array [1, 2, 3, 4, 5] after rotating by 3  gives [ 4, 5, 1, 2, 3].

Approach 1:

Use then temporary array to hold elements to shift at the end. Now shift remaining elements to the front. Append elements in temp array to end.

Approach 2:

Shift one element at a time. This way you will have to move all elements till required rotations are not achieved.

Approach 3:

Reverse elements to be shifted first. Then reverse remaining elements in place then reverse the whole array.

Example: 1, 2, 3, 4, 5 rotate left by 3 then

3, 2, 1, 4 ,5 -> Step1

3, 2, 1, 5, 4 -> Step 2

4, 5, 1, 2, 3 -> Step 3 

Below is the code for this approach.

public class ArrayRotation {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int size = array.length;
        int rotations = 3;

        array = rotate(array, 0, rotations - 1);
        array = rotate(array, rotations, size - 1);
        array = rotate(array, 0, size - 1);

        for (int i = 0; i < size; i++)
            System.out.print(array[i] + " ");

    }

    public static int[] rotate(int[] array, int start, int rotation) {
        for (int i = start; i < rotation; i++, rotation--) {
            int temp = array[i];
            array[i] = array[rotation];
            array[rotation] = temp;
        }
        return array;
    }
}

Comments are welcome.

Surpasser Count of each element in an array

Given an array of distinct integers, for each element of the array count the number of elements to the right that are greater than that element.

A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j].

Example:

input = [6, 5, 4, 7, 2, 8, 0]

output= [2, 2, 2, 1, 1, 0, 0]

Approach 1:

Simplest approach to iterate every time throught the array and find out greater element to it's right. This approach would require O(n^2) complexity and no space complexity.

Approach 2:

We can use O(n)  extra space and solve this efficiently. Priority queue can be used here to store the element in sorted order so that we can check the number of greater element in faster manner. So the complexity will be similar to the time required to push element to priority queue and removing from the same to check for greater element.

Steps:

Start from rear end of array, pick one element each time

Check if queue head is greater than current element 
if yes means all the element in queue are greater than current element.

Save the size of queue as output for specific index of input array

if no then remove element from queue and store it to stack for temporaty storage.
Go to step 1 again



Approach 2 is implemented in solution below.

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class SurpasserCount {
    public static void main(String[] args) {
        int[]  input = {6, 5, 4, 7, 2, 8, 0};
        int[] output = new int[input.length];

        Queue queue = new PriorityQueue();
        Stack stack = new Stack();

        for ( int i = input.length -1; i >= 0; i-- ){
            while (!queue.isEmpty()) {
                if (queue.peek() > input[i]) {
                    output[i] = queue.size();
                    break;
                } else {
                    stack.push(queue.remove());
                }
            }
            if (queue.isEmpty())
                output[i]=0;

            while (!stack.isEmpty()){
                queue.add(stack.pop());
            }

            queue.add(input[i]);
        }

        for (int i: output) {
            System.out.print(i + " ");
        }
    }
}
 

Comments are welcome.
Problem Source 

Check if Substrings are palindrome

Given a string and several queries on substrings of the given input string, check whether the substring is a palindrome or not.

Approach 1:

Simplest approach is to get the substring and check if the substring is palindrome or not. This can be done directly checking each character with its reverse position. 

This way you will have to check palindrome for all the input queries.

Approach 2:

We can find out all the palindrome in the string using dynamic programming in o(n^2) complexity and then use the DP solution return result for each query.   

To find out if string is palindrome we will follow below method:

• String with size 1 is palindrome
• String with size 2 is palindrome if both characters are same
• String with size 3 or more is the palindrome if characters in between are a palindrome.

Solution below implements the approach 2:

import java.util.Scanner;

public class Palindrome {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        int queryI = sc.nextInt();
        int queryJ = sc.nextInt();

        int length = str.length();

        boolean[][] dp = new boolean[length][length];

        for (int diff = 0; diff < str.length(); diff++) {
            for (int i = 0, j = diff; j < str.length(); i++, j++) {
                switch (diff) {
                    case 0:
                        dp[i][j] = true;
                        break;
                    case 1:
                        dp[i][j] = str.charAt(i) == str.charAt(j);
                        break;
                    default:
                        dp[i][j] = dp[i + 1][j - 1] && str.charAt(i) == str.charAt(j);
                        break;
                }
            }
        }

        System.out.println("Substring from " + queryI + " to " + queryJ + " is palindrome : "  + dp[queryI][queryJ]);
    }
}

Comments are welcome.

Find median in a running stream of integers

Problem
Given running stream of integers ( or read from dataset ), find out median of the stream you got so far. 
To understand this problem better consider stream as 7, 3, 9, 12.

When you have read 7 : Median 7
When you have read 7, 3 : Median 5 
When you have read 7, 3, 9 : Median 7
When you have read 7, 3, 9, 12 : Median 8

Approach 1:
You can use two priority queues. First would be Minimum priority Q and second would be maximum priority Q. Goal is to arrange number so that min priority Q would have numbers greater than median and max priority Q would have numbers less than median. Also after entering the numbers in Q we would balance the queues such that both Q should have equal element or one less element than other Q. So that median can be always top element from either of the queue.


Approach 2:
You can implement self balancing tree and put the values in tree such as; values less than median would be put to left of root and values greater than median would be pushed to write of the tree root. With this approach, root would be a median in case of odd number of elements.

Solution below implements approach 1. 

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class test {

    public static void main(String args[]) {

        PriorityQueue minQ = new PriorityQueue(10);
        PriorityQueue maxQ = new PriorityQueue(10, Collections.reverseOrder());

        int i = 0;

        Scanner sc = new Scanner(System.in);
        int median = 0;
        while (i++ < 10)
        {
            int val = sc.nextInt();
            if(i == 1) {
                maxQ.add(val);
                System.out.println("Median : " + val );
                median = val;
            }
            else{
                if ( val > median)
                    minQ.add(val);
                else
                    maxQ.add(val);

                int diff = 0;
                do {
                    diff = Math.abs( maxQ.size() - minQ.size() );
                    if (diff == 0) {
                        median = (maxQ.peek() + minQ.peek()) / 2;
                        break;
                    } else {
                        if (diff == 1) {
                            if (maxQ.size() > minQ.size())
                                median = maxQ.peek();
                            else
                                median = minQ.peek();
                            break;
                        } else {
                            //If queues is not balanced, balance the queues
                            PriorityQueue high = maxQ.size() > minQ.size() ? maxQ : minQ;
                            PriorityQueue low = maxQ.size() > minQ.size() ? minQ : maxQ;
                            low.add(high.poll());
                        }
                    }
                }while (diff > 1);

                System.out.println("Median : " + median );
            }
        }

    }
}

Comments are welcome.

Add two linked list

Problem
You have given two linked list, which can be of same length or different. You have to add these lists and return sum in new list.
E.g: lists are 1 -> 2 -> 3 -> 4   & 5 -> 6 -> 7 -> 8 Sum would be 6->9->1->2

Approach 1:
Simplest solution is to reverse the lists and add from last and reverse the result and original lists as well.
We can also generate the result in reverse order as well so that we need not to reverse the result but only reverse original lists.

Solution below implement this approach.

public class test {

    public static void main(String args[]) {

        SllNode head1 = new SllNode(1);
        head1.next = new SllNode(2);
        head1.next.next = new SllNode(3);
        head1.next.next.next = new SllNode(4);


        SllNode head2 = new SllNode(5);
        head2.next = new SllNode(6);
        head2.next.next = new SllNode(7);
        head2.next.next.next = new SllNode(8);
        head2.next.next.next.next = new SllNode(9);

        SllNode newH = AddSLL(head1, head2);
        DisplaySll(newH);

    }

    public static void DisplaySll(SllNode head){
        while (head != null){
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println("");
    }

    public static SllNode AddSLL(SllNode head1, SllNode head2){

        if(head1 == null){
            return head2;
        }

        if (head2 == null){
            return head1;
        }

        head1 = ReverseList(head1);
        head2 = ReverseList(head2);

        SllNode tempHead1 = head1;
        SllNode tempHead2 = head2;

        SllNode headN = new SllNode(0);
        int carry = 0;

        while (head1 != null && head2 != null){
            int sum = carry + head1.data + head2.data;
            headN.data = sum %10;
            carry = sum/10;
            SllNode temp = new SllNode();
            temp.next = headN;
            headN = temp;
            head1 = head1.next;
            head2 = head2.next;
        }

        while (head1!= null){
            int sum = carry + head1.data;
            headN.data = sum %10;
            carry = sum/10;
            SllNode temp = new SllNode();
            temp.next = headN;
            headN = temp;
            head1 = head1.next;
        }

        while (head2!= null){
            int sum = carry + head2.data;
            headN.data = sum %10;
            carry = sum/10;
            SllNode temp = new SllNode();
            temp.next = headN;
            headN = temp;
            head2 = head2.next;
        }

        if(carry > 0){
            headN.data = carry;
        }
        else {
            SllNode temp = headN;
            headN = headN.next;
            temp = null;
        }

        //If required reverse original lists
        head1 = ReverseList(tempHead1);
        head2 = ReverseList(tempHead2);

        return headN;
    }

    public static SllNode ReverseList(SllNode head){

        SllNode prevNode = null;

        while (head != null){
            SllNode temp = head;
            SllNode newHEad = head.next;
            head.next = prevNode;
            head = newHEad;
            prevNode = temp;
        }
        return prevNode;
    }

    static class SllNode{
        public int data;
        public SllNode next;

        public SllNode(){
            next = null;
        }

        public SllNode(int val){
            next = null;
            this.data = val;
        }

        public SllNode(int val, SllNode nextNode){
            next = nextNode;
            data = val;
        }
    }
}

Approach 2:
If we do not want to reverse the list, we can use recursive approach to find the sum.
Solution below implement this approach.

public class test {

    public static void main(String args[]) {

        SllNode head1 = new SllNode(1);
        head1.next = new SllNode(1);
        head1.next.next = new SllNode(1);
        head1.next.next.next = new SllNode(1);


        SllNode head2 = new SllNode(9);
        head2.next = new SllNode(9);
        head2.next.next = new SllNode(9);
        head2.next.next.next = new SllNode(9);
        head2.next.next.next.next = new SllNode(9);


        DisplaySll(head1);
        DisplaySll(head2);
        SllNode newH = AddWithoutReverse(head1, head2);
        System.out.println("with recursion : ");
        DisplaySll(newH);

    }

    public static int FindLength(SllNode head){
        int lenght = 0;
        while (head != null){
            head = head.next;
            lenght++;
        }
        return lenght;
    }

    public static SllNode AddWithoutReverse(SllNode head1, SllNode head2){
        if(head1 == null){
            return head2;
        }

        if (head2 == null){
            return head1;
        }

        int length1 = FindLength(head1);
        int length2 = FindLength(head2);

        SllNode tempHead = head1;
        SllNode tempHead2 = head2;

        if(length1 != length2){
            int l1 = length1;
            int l2 = length2;
            if(l1 > l2){
                while (l1 > l2){
                    tempHead = tempHead.next;
                    l1--;
                }
            }
            else {
                while (l2 > l1){
                    tempHead2 = tempHead2.next;
                    l2--;
                }
            }
        }

        SllNode listSum = SllAdd(tempHead, tempHead2);
        int carry = 0;
        if (listSum.data /10 > 0){
            carry = listSum.data/10;
            listSum.data = listSum.data%10;
        }

        SllNode remaining = null;
        if(length1 != length2) {
            if(length1 > length2){
                remaining = AddSingle(head1, carry, length1, length2);

            }
            else {
                remaining = AddSingle(head2, carry, length2, length1);
            }
        }
        SllNode rHead = remaining;
        while (remaining.next != null){
            remaining = remaining.next;
        }
        remaining.next = listSum;

        if (rHead.data /10 > 0){
            carry = rHead.data/10;
            rHead.data = rHead.data%10;
            SllNode temp = new SllNode(carry, rHead);
            rHead = temp;
        }

        return rHead;
    }

    private static SllNode AddSingle(SllNode head, int carry, int length1, int length2){
        if(length1-1 > length2){
            SllNode temp = new SllNode();
            temp.next = AddSingle(head.next, carry, length1-1, length2);
            temp.data = temp.next.data/10 + head.data;
            temp.next.data = temp.next.data % 10;
            return temp;
        }

        SllNode newNode = new SllNode();
        newNode.data = carry + head.data;
        return newNode;
    }


    private static SllNode SllAdd(SllNode h1, SllNode h2){
        if(h1 != null && h2 != null){
            SllNode sumNode = new SllNode();
            sumNode.next = SllAdd(h1.next, h2.next);
            int carry = 0;
            if(sumNode.next != null){
                carry = sumNode.next.data / 10;
                sumNode.next.data = sumNode.next.data % 10;
            }
            sumNode.data = h1.data + h2.data + carry;
            return sumNode;
        }
        return null;
    }

    public static void DisplaySll(SllNode head){
        while (head != null){
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println("");
    }


    static class SllNode{
        public int data;
        public SllNode next;

        public SllNode(){
            next = null;
        }

        public SllNode(int val){
            next = null;
            this.data = val;
        }

        public SllNode(int val, SllNode nextNode){
            next = nextNode;
            data = val;
        }
    }
}

Comments are welcome.