Cycle Detection in LinkedList

Say, we have a linked list
    6->8->9->10->4->3->10.....

If last but one node points to 10, then we will end up in an infinite loop.
So the question here is - how to detect this cycle.

This can be identified using the Floyd Cycle detection algorithm.

http://en.wikipedia.org/wiki/Cycle_detection 

This algorithm is also known as Tortoise and Hare algorithm, In this we will have two references, one reference jumps to one position and other one jumps to 2 positions, we do this continuously until we iterate all the elements from both the references or if both the reference points to same node, In each iteration we will compare the node value from reference one and two.

Below is the simple java code to find the cycle detection.

Here we have introduced two references
first and second,  
Iteration 1, first -> 6, second ->8
Iteration 2, first -> 8, second ->10
Iteration 3, first -> 9, second ->3
Iteration 4, first -> 10, second ->4
Iteration 5, first -> 4, second ->10
Iteration 6, first -> 3, second ->3

At iteration 6, both the node values will be equal and we stop the iteration.

 


 
     public static boolean isCyclic(LinkedList list) {
        LinkedList.Node first = list.head(); // get the head node
        LinkedList.Node second = list.head.getNext(); // get the second node
       
        while(true) {
            if(first !=null && second != null && first.getData() != null && second.getData() !=null) {
                if(first.getData().equals(second.getData())) {
                    return true;
                } else {
                    first = first.getNext();
                    if(second.getNext() != null)
                        second = second.getNext().getNext();
                    else
                        second =  null;
                }
            } else
                return false;
        }
    }

How to Merge two sorted arrays in O(n) time

Assume that we have two sorted arrays and we want to merge both the arrays efficiently into a single sorted array.

The algorithm we are going to use is - kind of DB sort merge Join algorithm.

While joining 2 tables in DB, DB sorts both the tables first and compare against the join columns.

For example, If we have two tables, Table A and Table B.

For simplicity, let us take only two columns.

empid	name
1	AAA
2	BBB
3	CCC
4	DDD
5	EEE
6	FFF

empid	ADDRESS
2	AAA
4	BBB
6	CCC

If we want to join these two tables using empid, then one among the DB join algorithm is Merge Join algorithm.

DB sorts these two tables using the join columns, In this case it would be empid.

It compares table 1 and table 2's empid.
Initially we start iterating each row, If the value of first table <  value of second table, then we ignore this row, Then we will iterate the next row only from first table.
Now we compare second row's value of first table against the first row value of second table, Bot matches it outputs this row.
Next we start iterating third row, Now if the value of first table > value of second table then we will start iterating from second table and continue the comparision.

In general, Initially we start with both the tables, After the comparison we will decide which table we want to iterate next, If left table value is smaller then we will iterate left table, If the right table value is small, we will iterate the right table. It continues until one among the table is iterated completely.


===============================================

The same principle applies to merge the sorted rows into a single sorted row.

Assume that we have the following arrays.

A = {1, 4, 6, 8, 10 }
B = { 2, 3, 5, 9 }


Now we want to merge these two arrays.

We start iterating both the arrays with two different variables, i and j refers to A and B.
Create an empty array with the length of (sum(Length A, Length B)).

If i < j then
start iterating values from B, add i to the new array then increment i.
else
start iterating values from B, add j to the new array then increment j.
Continue the iteration until i<A.length or j<B.length.

Now do the individual iterations of A and B seperately.
A:
Iterate until i<A.length.
    Get the element and add it to new Array.
B:

Iterate until j<B.length.
    Get the element and add it to new Array.

The Java code for this algorithm is given below.

In the example mentioned above, the first while loop would iterate for 8 times, second while loop iterate for 1 time, third for none, because of Length of B < Length of A.

The below code would complete the operation in O(n).



private static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length+b.length];
        int i=0, j=0;
        int k=0;
   
        while(i<a.length && j<b.length) {
            if(a[i]<=b[j]) {
                c[k] = a[i];
                i++;
            } else {
                c[k] = b[j];
                j++;
            }
            k=k+1;
        }
   
        while(i<a.length) {
            c[k] = a[i];
            i++;
            k=k+1;
        }

        while(j<b.length) {
            c[k] = b[j];
            j++;
            k=k+1;
        
        }
        System.out.println(k+"**********");
        return c;
    }

Adding Two Numbers using Linked List

In this blog, we will see adding two numbers using a LinkedList with the time complexity of O(n).

Represent both the numbers using Linked List in the reverse order.
For example, if we want to add two numbers

1234 +46 = 1280

LinkedList 1 would represent the values in the form of 4->3->2->1
LinkedList 2 would represent the values in the form of 6 -> 4

The resultantList will have the value as 1->2->8->0
  

The below code would iterate both the linkedlist as the same time.
Here is the algorithm.

1. Get the reference of both the LinkedList's head node and declare a flag to Identify whether the sum has 2 digits.
Iterate until node1.getData is not null or  node2.getData is not null

2. Get the values associated to the node and store it in a different variables.

3. Add both the values
4. For the first iteration, carried flag will be false.
       From second iteration onwards, this flag might be true depending upon the carried number, If we add 8 + 4, the carried number will be 1 here.
      If we have carried number then
           a. Get the head node value
           b. add it to the sum.
           c. remove the head node.
           d. Mark the carried flag as false.

5. If the number of digits is 2
    a)      then split the digits as ones and tens.
        For example if the sum is 12
          ones -> 2
          tens -> 1
        
        Add ones and tens to the resultant List
Such that the resultantList head always holds the value of the carried over number, In this case the head will have the value as 1, the subsequent node will have the value as 2.

    b.  If the sum value is single digit then
         Add the value to the resultant Linked List.

6. Traverse to the next node from List1 and List2, so that node1 -> node1.next, node2 -> node.next
7. Repeat the steps until both the list are completely traversed.
             

The below java code, iterates all the nodes in the list only one time, so we get the O(n) complexity.
The code inside the while loop are all constant time operations.

public static LinkedList add(LinkedList list1, LinkedList list2) {

        Node node1 = list1.head;

        Node node2 = list2.head;

        LinkedList returnList = new LinkedList();

        boolean isCarried = false;

        while((node1 != null && node1.getData() !=null) || (node2 !=null && node2.getData() != null)) {

            int k=0;

            int l=0;

            if(node1 != null && node1.getData() !=null) {

                k = Integer.valueOf(node1.getData());

            }

            if(node2 != null && node2.getData() !=null) {

                l = Integer.valueOf(node2.getData());

            }

            int m = k + l;

            if(isCarried) {

                isCarried = false;

                m += Integer.valueOf(returnList.head.getData());

                returnList.remove(0);

            }

            String value = String.valueOf(m);

            if(value.length()==2) {

                returnList.add(0, value.substring(1));

                returnList.add(0, value.substring(0,1));

                isCarried = true;

            } else {

                returnList.add(0, value);

            }

            if(node1 != null) {

                node1 = node1.getNext();

            }

            if(node2 != null) {

                node2 = node2.getNext();

            }

        }

        return returnList;

    }