CC150

1.1.UniqChar.java

// solution is of O(n^2) time complexity
public class UniqChar {
    public static void main(String[] args) {
        String str = args[0];
        int N = str.length();
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    System.out.println("There are same characters in the string");
                    break;
                }
            }
        }
    }
}

class RightUniqChar {

    // right answer, with O(n) time complexity, ASCII only
    public static boolean RightUniqChar(String str) {
        if (str.length() > 256) return false;

        boolean[] chars = new boolean[256];
        for (int i = 0; i < str.length(); i++) {
            int var = str.charAt(i);
            if(chars[var]) {
                return false;
            }
            chars[var] = true;
        }
        return true;
    }

    // **** advanced answer which I don't understand, bit manipulation, a-z only
    public static boolean AdvancedUniqChar(String str) {
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i) - 'a';

            if ((checker & (1 << val)) > 0) return false;

            checker |= (1 << val);
        }
        return true;
    }
}

1.2.ReversedStr.java

/**********
Usage:

java ReverseStr abcd

**********/

public class ReverseStr {

    public static String reversed(String str) {
        int N = str.length();
        String[] r_str = str.split("");
        for(int i = 0; i < N/2; i++) {
            String temp = r_str[i];
            r_str[i] = r_str[N-i-1];
            r_str[N-i-1] = temp;
        }

        String result = String.join("", r_str);   // This is Java 8 only
        return result;
    }

    public static void main(String[] args) {
        String s = reversed(args[0]);
        System.out.println(s);
    }
}

class RightReversedStr {

    // Method 1, without using packages
    public static String rightReverse(String input) {
        char[] in = input.toCharArray();
        int begin=0;
        int end=in.length-1;
        char temp;
        while(end>begin){
            temp = in[begin];
            in[begin]=in[end];
            in[end] = temp;
            end--;
            begin++;
        }

        return new String(in);
    }

    // Method 2, with package StringBuffer
    public static void simpleReverse(String str) {
        String reversedStr = new StringBuffer(str).reverse().toString();
        System.out.println(reversedStr);
    }

    public static void main(String[] args) {
        System.out.println(rightReverse(args[0]));
        simpleReverse(args[0]);
    }
}

1.3.CheckPermutation.java

public class CheckPermutation {

    // perform quick sort on char array, with first element in array as pivot
    public static void QuickSort(char[] strArr, int start_idx, int end_idx) {

        if (start_idx != end_idx) {
            char pivot = strArr[start_idx];
            int temp_idx = start_idx;
            for(int i = start_idx; i < end_idx; i++) {
                if (strArr[i] < pivot) {
                    char temp = strArr[temp_idx];
                    strArr[temp_idx] = strArr[i];
                    strArr[i] = temp;
                    temp_idx++;
                }
            }

            QuickSort(strArr, start_idx, temp_idx);
            QuickSort(strArr, temp_idx+1, end_idx);
        }
    }

    // sort two input arrays then compare for equivalence
    // if the sorted arrays are equal, then one must be a permutation of the other
    public static void main(String[] args) {
        if (args[0].length() != args[1].length()) {
            System.out.println("Second string is not the permutation of the first string");
            return;
        }

        char[] firstStr  = args[0].toCharArray();
        char[] secondStr = args[1].toCharArray();
        int N = firstStr.length;
        QuickSort(firstStr, 0, N);
        QuickSort(secondStr, 0, N);

        for (int i = 0; i < N; i++) {
            if (firstStr[i] != secondStr[i]) {
                System.out.println("Second string is not the permutation of the first string");
                return;
            }
        }

        System.out.println("Second string is the permutation of the first string");
    }
}


class AnswerSolution {

    // Solution 1
    public String sort(String s) {
        char[] content = s.toCharArray();
        java.util.Arrays.sort(content);
        return new String(content);
    }

    public boolean permutation_one(String s, String t) {
        if (s.length() != t.length()) return false;
        return sort(s).equals(sort(t));
    }

    // Solution 2, ASCII only
    public boolean permutation_two(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] chars = new int[256];

        char[] s_array = s.toCharArray();
        for (char c : s_array) {
            chars[c]++;
        }

        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (--chars[c] < 0) return false;
        }
        return true;
    }
}

1.4.ReplaceBlank.java

public class ReplaceBlank {
    public static String replace(String str) {

        int N = str.length();
        int num = N;

        // calculate length of new array
        for (int i = 0; i < N; i++) {
            if (str.charAt(i) == ' ') num += 2;
        }

        char[] newStr = new char[num];

        // construct new string
        int j = 0;
        for (int i = 0; i < N; i++) {
            if (str.charAt(i) == ' ') {
                newStr[j] = '%';
                newStr[j+1] = '2';
                newStr[j+2] = '0';
                j += 2;
            } else {
                newStr[j] = str.charAt(i);
            }
            j++;
        }

        return new String(newStr);
    }

    public static void main(String[] args) {
        String replacedStr = replace(args[0]);
        System.out.println(replacedStr);
    }
}


// 答案很诡异，所以不贴了，唯一可取之处是倒叙插值给原数组转换成的字符数组的话，可以省一个数组

1.5.CompressSameChar.java

public class CompressSameChar {

    public static String compressStr(String str) {
        // create a new char array that is of the same length as the input string
        int N = str.length();
        char[] newStrArr = new char[N];
        // hold current char count
        int sameCount = 1;
        // initialize new index number for new char array
        int newIdx = 0;

        for (int i = 0;i <= N-1; i++) {
            // compare current char with the next char, if same, add char count
            if (i < N-1 && str.charAt(i) == str.charAt(i+1)) {
                sameCount += 1;
            // if not same, or index at the last char, append current char and count number to the new array
            } else {
                newStrArr[newIdx] = str.charAt(i);
                char[] num_chars = ("" + sameCount).toCharArray();
                for (int j = 0; j < num_chars.length; j++) {
                    // check if new array is larger than the string
                    if (newIdx >= N-1) return str;
                    newIdx++;
                    newStrArr[newIdx] = num_chars[j];
                }
                if (newIdx >= N-1) return str;
                newIdx++;
                sameCount = 1;
            }
        }
        return new String(newStrArr);
    }

    public static void main(String[] args) {
        System.out.println(compressStr(args[0]));
    }
}

1.6.RotateImg.java

public class RotateImg public class RotateImg {

    // left rotate
    public static char[][] LeftRotateStr(char[][] charsArr) {
        int N = charsArr.length;
        char[][] rotatedMrx = new char[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = N-1; j >= 0; j--) {
                rotatedMrx[N-1-j][i] = charsArr[i][j];
            }
        }
        return rotatedMrx;
    }

    // right rotate
    public static char[][] RightRotateStr(char[][] charsArr) {
        int N = charsArr.length;
        char[][] rotatedMrx = new char[N][N];
        for (int i = N-1; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                rotatedMrx[j][N-1-i] = charsArr[i][j];
            }
        }
        return rotatedMrx;
    }

    public static void main(String[] args) {
        // initialize matrix
        int N = args[0].length();
        char[][] charsArr = new char[N][N];
        int idx = 0;
        for (String arg : args) {
            System.out.println(arg);
            char[] strArr = arg.toCharArray();
            charsArr[idx] = strArr;
            idx++;
        }

        // print left rotate matrix
        System.out.println("\n");

        char[][] lRotateMrx = LeftRotateStr(charsArr);

        for (int i = 0; i < N; i++) {
            String str = new String(lRotateMrx[i]);
            System.out.println(str);
        }

        // print right rotate matrix
        System.out.println("\n");

        char[][] rRotateMrx = RightRotateStr(charsArr);

        for (int i = 0; i < N; i++) {
            String str = new String(rRotateMrx[i]);
            System.out.println(str);
        }
    }


}

1.7.CrossZero.java

import java.util.Arrays;

public class ZeroCross {
    public static int[][] spotZero(int[][] matrix) {
        int rowNum       = matrix.length;
        int columnNum    = matrix[0].length;
        int[] rblankMark = new int[rowNum];
        int[] cblankMark = new int[columnNum];

        // mark row and column with zeros
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < columnNum; j++) {
                if (matrix[i][j] == 0) {
                    rblankMark[i] = 1;
                    cblankMark[j] = 1;
                }
            }
        }

        // cross row with zero
        for (int i = 0; i < rowNum; i++) {
            if (rblankMark[i] == 1) {
                for (int j = 0; j < columnNum; j++) {
                    matrix[i][j] = 0; // int always have initial value of 0
                }
            }
        }

        // cross column with zero
        for (int i = 0; i < columnNum; i++) {
            if (cblankMark[i] == 1) {
                for (int j = 0; j < rowNum; j++) {
                    matrix[j][i] = 0;
                }
            }
        }

        return matrix;
    }

    public static void main(String[] args) {
        int rowNum = args.length;
        int columnNum = args[0].length();
        int[][] intMrx = new int[rowNum][columnNum];
        for (int i = 0; i < rowNum; i++) {
            String str = args[i];
            System.out.println(str);
            for (int j = 0; j < columnNum; j++) {
                intMrx[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        int[][] resultMrx = spotZero(intMrx);
        for (int i = 0; i < rowNum; i++) {
            System.out.println(Arrays.toString(resultMrx[i]));
        }

    }
}

1.8.CheckRotation.java

public class CheckRotation {
    public static void main(String args[]) {
        if (args[0].length() != args[1].length()) {
            System.out.println("The second string is not the rotation of the first string")
        } else {
            if (IsSubstring(args[0] + args[0], args[1])) {
                System.out.println("The second string is not the rotation of the first string")
            } else {
                System.out.println("The second string is not the rotation of the first string")
            }
        }
    }
}

2.1.RemoveDup.java

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }
}

public class RemoveDup {

    // print current linked list
    public static void printList(LinkedListNode<Integer> node) {
        while(node.next != null) {
            System.out.println(node.data);
            node = node.next;
        }
        System.out.println(node.data);
    }

    // remove the duped node in the list
    public static void RemoveDup(String[] strs) {
        // construct linked list
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1;  i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }

        // print original list
        printList(node);
        System.out.println("\n");

        // remove duplicate in linked list
        LinkedListNode<Integer> priorP = node;
        LinkedListNode<Integer> postP  = node;
        while (priorP != null) {
            postP  = priorP;
            while(postP != null && postP.next != null) {
                if(priorP.data == postP.next.data) {
                    LinkedListNode<Integer> newNode = postP.next.next;
                    if (newNode != null) newNode.before = postP;
                    postP.next = newNode;
                } else {
                    postP = postP.next;
                }
            }
            priorP = priorP.next;
        }

        // print adapted list
        printList(node);

    }

    public static void main(String[] args) {
        RemoveDup(args);
    }
}

2.2.FindKToLast.java

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}

public class FindKToEnd {

    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1;  i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }
        return node;
    }

    public static void FindKToEnd(String[] strs, int k) {
        LinkedListNode<Integer> head = constructList(strs);

        head.printList();

        LinkedListNode<Integer> priorP = head;
        LinkedListNode<Integer> postP  = head;

        // print out data of Kth node to end node of linked list
        int i = 1;
        while(priorP != null) {
            priorP = priorP.next;
            if(i > k) {
                postP = postP.next;
            }
            i += 1;
        }

        postP.printList();
    }

    public static void main(String[] args) {
        int N = 3;
        FindKToEnd(args, N);
    }

}

2.3.DeleteMiddle.java

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}


public class DeleteMiddle {
    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1; i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }
        return node;
    }

    public static void DeleteMiddle(LinkedListNode<Integer> head) {
        LinkedListNode<Integer> priorP = head;
        LinkedListNode<Integer> postP  = head;
        while(priorP.next != null) {
            priorP = priorP.next;
            // if even number middle
            if(priorP.next == null) {
                LinkedListNode<Integer> newNode = postP.next.next;
                newNode.before = postP;
                postP.next = newNode;
                DeleteMiddle(head);
                break;
            }

            // if odd number middle
            if(priorP.next.next == null) {
                LinkedListNode<Integer> newNode = postP.next.next;
                newNode.before = postP;
                postP.next = newNode;
                break;
            }

            priorP = priorP.next;
            postP  = postP.next;

        }

    }


    public static void main(String[] args) {
        LinkedListNode<Integer> head = constructList(args);
        head.printList();
        DeleteMiddle(head);
        head.printList();
    }
}

2.3.DelMiddle.java

public class DelMiddle {
    public static void DelMiddle(LinkedListNode<Integer> middle) {
        middle.data = middle.next.data;
        middle = middle.next.next;
    }
}

2.4.DivideList.java

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}


public class DivideList {

    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1; i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }
        return node;
    }

    public static LinkedListNode<Integer> DivideList(LinkedListNode<Integer> head, int x) {
        // iterate the list, if data in node greater than given x, delete and append to new node
        LinkedListNode<Integer> xNode = new LinkedListNode<Integer>(x);
        LinkedListNode<Integer> newNode = xNode;
        LinkedListNode<Integer> headCopy = head;

        while(head.next != null) {
            LinkedListNode<Integer> currNode = head.next;
            // if node value larger than value
            if (currNode.data >= x) {
                // Delete node
                head.next = currNode.next;
                currNode.next = null;
                // Then append node to a new linked list
                newNode.next = currNode;
                newNode = newNode.next;
            } else {
                head = head.next;
            }
        }

        head.next = xNode.next;

        // handle head separately
        if(headCopy.data >= x) {
            LinkedListNode<Integer> newHead = headCopy.next;
            if (head.next != null) {
                newNode.next = headCopy;
                headCopy.next = null;
                return newHead;
            } else {
                head.next = headCopy;
                headCopy.next = null;
                return newHead;
            }
        } else {
            LinkedListNode<Integer> newHead = headCopy;
            return newHead;
        }

    }

    public static void main(String[] args) {
        LinkedListNode<Integer> head = constructList(args);
        head.printList();
        LinkedListNode<Integer> newHead = DivideList(head, 7);
        newHead.printList();
    }

}

2.5.AddNodeDigit.java

import java.util.NoSuchElementException;

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}

public class AddNodeDigit {
    public static void AddNodeDigit(LinkedListNode<Integer> priorHead, LinkedListNode<Integer> postHead ) {

        // Check if Linked list exists
        if (priorHead == null) throw new NoSuchElementException();
        if (postHead  == null) throw new NoSuchElementException();

        // set carry flag to 0
        int carryFlag = 0;

        while(priorHead != null && postHead != null) {
            int val = priorHead.data + postHead.data + carryFlag;

            // handle carry flag
            if (val - 10 >= 0) {
                val = val - 10;
                carryFlag = 1;
            } else {
                carryFlag = 0;
            }

            // assign result data to prior linked list
            priorHead.data = val;

            // handle last carry flag
            if(priorHead.next == null && postHead.next == null) {
                if (carryFlag == 1) {
                    priorHead.next = new LinkedListNode<Integer>(1);
                }
                break;
            }

            // handle priorHead out of bound
            if(priorHead.next == null && postHead.next != null) {
                priorHead.next = new LinkedListNode<Integer>(0);
            }

            // handle postHead out of bound
            if(postHead.next == null && priorHead.next != null) {
                postHead.next = new LinkedListNode<Integer>(0);
            }

            priorHead = priorHead.next;
            postHead = postHead.next;

        }
    }

    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs, int N) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1; i < N; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }
        return node;
    }

    // Follow up question
    public static LinkedListNode<Integer> reverseList(LinkedListNode<Integer> head) {
        LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(head.data);
        while(head.next != null) {
            LinkedListNode<Integer> newHead = new LinkedListNode<Integer>(head.next.data);
            newHead.next = newNode;
            newNode = newHead;
            head = head.next;
        }

        return newNode;
    }


    public static void main(String[] args) {

        LinkedListNode<Integer> priorHead = constructList(args, 3);
        LinkedListNode<Integer> postHead  = constructList(args, 2);

        // Follow up
        LinkedListNode<Integer> reversedPrior = reverseList(priorHead);
        LinkedListNode<Integer> reversedPost = reverseList(postHead);


        priorHead.printList();
        postHead.printList();
        AddNodeDigit(priorHead, postHead);
        priorHead.printList();


        // Follow up
        AddNodeDigit(reversedPrior, reversedPost);
        priorHead = reverseList(reversedPrior);
        priorHead.printList();

    }
}

2.6.CheckCircle.java

import java.util.NoSuchElementException;

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}

public class CircleCheck {

    public static LinkedListNode<Integer> CircleCheck(LinkedListNode<Integer> head) {
        LinkedListNode<Integer> priorHead = head;
        LinkedListNode<Integer> postHead  = head;
        System.out.println(priorHead.data);

        // first collision
        priorHead = priorHead.next;
        priorHead = priorHead.next;
        postHead  = postHead.next;

        while (priorHead != postHead) {
            priorHead = priorHead.next;
            priorHead = priorHead.next;
            postHead  = postHead.next;
        }

        // second collision
        priorHead = head;
        while (priorHead != postHead) {
            priorHead = priorHead.next;
            postHead  = postHead.next;
        }

        System.out.println(priorHead.data);
        return priorHead;
    }

    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1; i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }

        // construct looped linked list
        LinkedListNode<Integer> head = node;
        while (head.next != null) {
            head = head.next;
        }
        head.next = node.next.next.next;

        return node;
    }

    public static void main(String[] args) {
        LinkedListNode<Integer> head = constructList(args);
        CircleCheck(head);
    }
}

2.7.CheckPalindrome.java

import java.util.NoSuchElementException;

//implement double linked list
class LinkedListNode<AnyType> {
    LinkedListNode<AnyType> next = null;
    LinkedListNode<AnyType> before = null;
    AnyType data;

    public LinkedListNode(AnyType d) {
        data = d;
    }

    void appendToTail(AnyType endNode) {
        LinkedListNode<AnyType> tail = new LinkedListNode<AnyType>(endNode);
        LinkedListNode<AnyType> n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = tail;
        tail.before = n;
    }

    void appendToHead(AnyType startNode) {
        LinkedListNode<AnyType> head = new LinkedListNode<AnyType>(startNode);
        LinkedListNode<AnyType> n = this;
        while (n.before != null) {
            n = n.before;
        }
        n.before = head;
        head.next = n;
    }

    // print current linked list
    void printList() {
        LinkedListNode<AnyType> head = this;
        while(head.next != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.print(head.data);
        System.out.println();
    }
}

public class CheckPalindrome {

    public static boolean CheckPalindrome(LinkedListNode<Integer> head) {
        LinkedListNode<Integer> reversedHead = reverseList(head);

        while (reversedHead != null) {
            if (reversedHead.data != head.data) {
                return false;
            }
            reversedHead = reversedHead.next;
            head = head.next;
        }
        return true;
    }

    // construct linked list from string array
    public static LinkedListNode<Integer> constructList(String[] strs) {
        int data = Integer.parseInt(strs[0]);
        LinkedListNode<Integer> node = new LinkedListNode<Integer>(data);
        for (int i = 1; i < strs.length; i++) {
            data = Integer.parseInt(strs[i]);
            node.appendToTail(data);
        }
        return node;
    }

    public static LinkedListNode<Integer> reverseList(LinkedListNode<Integer> head) {
        LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(head.data);
        while(head.next != null) {
            LinkedListNode<Integer> newHead = new LinkedListNode<Integer>(head.next.data);
            newHead.next = newNode;
            newNode = newHead;
            head = head.next;
        }

        return newNode;
    }

    public static void main(String[] args) {
        LinkedListNode<Integer> head = constructList(args);
        head.printList();
        System.out.println(CheckPalindrome(head));
    }
}

3.1.ArrayStack.java

// TODO: This solution has type checking issues
import java.util.NoSuchElementException;

public class ArrayStack<Item> {

    int    arraySize = 0;
    int    stackSize = 0;
    int[]  pointers = new int[3];
    Item[] arr = (Item[]) new Object[arraySize];

    // Constructor, kind of like the initialize in ruby and __init__ in python
    public ArrayStack(int arraySize) {
        this.arraySize = arraySize;
        arr       = (Item[]) new Object[arraySize];
        // Round the number
        stackSize = (int)Math.rint(arraySize/3.0);
        System.out.println(stackSize);
        pointers[0]  = -1;
        pointers[1]  = -1+stackSize;
        pointers[2]  = -1+stackSize*2;

    }

    // stack number can only be 0, 1, 2
    public void push(int stackNum, Item item) {
        if (pointers[stackNum] == (stackNum+1)*stackSize-1) throw new NoSuchElementException();
        pointers[stackNum]++;
        arr[pointers[stackNum]] = item;
    }

    public Item pop(int stackNum) {
        if (pointers[stackNum] == stackNum*stackSize-1) throw new NoSuchElementException();
        Item item = arr[pointers[stackNum]];
        arr[pointers[stackNum]] = null;
        pointers[stackNum]--;
        return item;
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this.arr) {
            s.append(item + " ");
        }
        return s.toString();
    }

    public static void main(String[] args) {
        int num = Integer.parseInt(args[0]);
        ArrayStack<Integer> stacks = new ArrayStack<Integer>(num);
        stacks.push(1, 2);
        stacks.push(0, 1);
        stacks.push(0, 1);
        stacks.push(2, 3);
        System.out.println(stacks.toString());
        stacks.pop(0);
        System.out.println(stacks.toString());

    }
}

3.2.StackMin.java

import java.util.NoSuchElementException;

// implement stack via linked list
class Node<Type extends Comparable<Type>>{
    Node<Type> next = null;
    Type data = null;

    public Node(Type d){
        data = d;
    }
}

class Stack<Type extends Comparable<Type>> {

    Node<Type> head;

    public Stack(Type d){
        head = new Node<Type>(d);
    }

    // 3 <- 2 <- 1  ====>  3 <- 2 <- 1 <- 0
    public void push(Type d) {
        if (head != null) {
            Node<Type> newHead = new Node<Type>(d);
            newHead.next = head;
            head = newHead;
        } else {
            head = new Node<Type>(d);
        }
    }

    // 3 <- 2 <- 1 <- 0  ====>  3 <- 2 <- 1
    public Type pop(){
        Type data = null;
        if (head == null) { throw new NoSuchElementException(); }
        data = head.data;
        if (head.next != null) {
            head = head.next;
        } else {
            head = null;
        }
        return data;
    }
}

// add subclass that keep the min value of the stack
public class StackMin<Type extends Comparable<Type>> extends Stack<Type>{

    // all variables are inherited from SuperClass
    // add new variable min
    Type min = null;

    // inherit constructor from SuperClass
    public StackMin(Type d){
        super(d);
    }

    // override push method in super class, take min into consideration
    @Override
    public void push(Type d){
        super.push(d);
        Type newD = d;
        if (min == null) min = head.data;
        if (newD.compareTo(min) < 0) min = d;
    }

    // override pop, but then it might take O(n) time to calculate min
    @Override
    public Type pop(){
        Type data = super.pop();
        if (data == min) {
            Node<Type> newHead = head.next;
            min = newHead.data;
            while(newHead != null) {
                min = (min.compareTo(newHead.data) < 0 ? min : newHead.data);
                newHead = newHead.next;
            }
        }
        return data;
    }

    // add new method getMin(), take O(1) time.
    public Type getMin(){
        return min;
    }

    // main method mainly for testing
    public static void main(String[] args) {
        StackMin<Integer> stack = new StackMin<Integer>(Integer.parseInt(args[0]));
        for (int i = 1; i < args.length; i++) {
            int item = Integer.parseInt(args[i]);
            stack.push(item);
        }
        System.out.println(stack.pop());
        System.out.println(stack.getMin());
    }

}

3.3.SetOfStacks.java

// implement stack via linked list and array
import java.lang.reflect.Array;
import java.util.NoSuchElementException;

// implement new Node that store the index of linked list and data as fixed array
class Node<Type>{
    Node<Type> next = null;
    Type[] data = null;
    int index;

    public Node(Type d, int size, int idx){
        Class<?> c = d.getClass();
        data = (Type[]) Array.newInstance(c, size);
        data[0] = d;
        index = idx;
    }
}

// implement set of stacks, where each stack is a array with a index
public class SetOfStacks<Type> {
    Node<Type> head;
    int stackSize;
    int currentSize;

    public SetOfStacks(Type d, int size) {
        head = new Node<Type>(d, size, 0);
        stackSize = size;
        currentSize = 0;
    }

    public void push(Type d) {
        if (currentSize < stackSize-1) {
            currentSize++;
            head.data[currentSize] = d;
        } else {
            int idx = head.index + 1;
            Node<Type> newHead = new Node<Type>(d, stackSize, idx);
            newHead.next = head;
            head = newHead;
            currentSize = 0;
        }
    }

    public Type pop() {
        Type data;
        data = head.data[currentSize];

        if (currentSize > 0) {
            currentSize--;
        } else {
            if (head.next == null) {throw new NoSuchElementException();}
            head = head.next;
            currentSize = stackSize-1;
        }
        return data;
    }

    // Because the order of index is opposite with the stack, the code here is
    // a little bit tedious, should find a better way.
    public Type popAt(int index) {
        Node<Type> tempHead = head;
        Type data;

        while (index != tempHead.index) {
            if (tempHead.next == null) {throw new NoSuchElementException();}
            tempHead = tempHead.next;
        }

        data = tempHead.data[stackSize-1];
        if (tempHead.index == head.index) {
            data = this.pop();
        } else {
            tempHead = head;
            while (tempHead.next.index >= index) {
                tempHead.next.data[stackSize-1] = tempHead.data[0];
                for (int i = 0; i < stackSize - 2; i++) {
                    tempHead.data[i] = tempHead.data[i+1];
                }
                tempHead = tempHead.next;
            }
            this.pop();
        }
        return data;
    }

    // main for test
    public static void main(String[] args){
        int initData = Integer.parseInt(args[0]);
        SetOfStacks<Integer> stacks = new SetOfStacks<Integer>(initData, 3);
        for(int i = 1; i < args.length; i++) {
            int data = Integer.parseInt(args[i]);
            stacks.push(data);
        }
        System.out.println(stacks.pop());
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));
        System.out.println(stacks.popAt(4));

    }
}

3.4.HanoiTower.java

public class HanoiTower {
    int plateNum;
    Tower towerOne;
    Tower towerTwo;
    Tower towerThree;

    // Constructor, initialize tower 1
    public HanoiTower(int pNum) {
        plateNum = pNum;
        towerOne    = new Tower(pNum, 1);
        towerTwo    = new Tower(pNum, 2);
        towerThree  = new Tower(pNum, 3);
        towerOne.fillTower();
    }

    // recursively move all disks
    public void moveDisks(int n, Tower origin, Tower buffer, Tower destination){
        // if there is nothing to move, return
        if (n <= 0) return;

        // move n-1 top disks to buffer
        moveDisks(n-1, origin, destination, buffer);

        // move top disk to destination
        moveTop(origin, destination);

        // move n-1 disks on buffer to destination
        moveDisks(n-1, buffer, origin, destination);
    }

    public void moveTop(Tower origin, Tower destination) {
        int plate = origin.pop();
        destination.push(plate);
        System.out.println("Move "+plate+ " from " + origin.index + " to " + destination.index);
    }

    public static void main(String[] args) {
        // initialize Hanoi towers
        int plateNum = Integer.parseInt(args[0]);
        HanoiTower towers = new HanoiTower(plateNum);

        // print out initial status of tower 1 and 3
        for(int i = 0; i < plateNum; i++) {
            System.out.print(towers.towerOne.stack[i]);
        }
        System.out.println();
        for(int i = 0; i < plateNum; i++) {
            System.out.print(towers.towerThree.stack[i]);
        }
        System.out.println();
        System.out.println();

        // do move recursively
        towers.moveDisks(plateNum, towers.towerOne, towers.towerTwo, towers.towerThree);

        // print out status of tower 1 and 3 after move operations
        System.out.println();
        for(int i = 0; i < plateNum; i++) {
            System.out.print(towers.towerOne.stack[i]);
        }
        System.out.println();
        for(int i = 0; i < plateNum; i++) {
            System.out.print(towers.towerThree.stack[i]);
        }
        System.out.println();
    }
}

class Tower {
    int plateNum;
    int[] stack;
    int top = 0;
    int index;

    public Tower(int pNum, int idx) {
        plateNum = pNum;
        stack = new int[plateNum];
        index = idx;
    }

    // initialize the tower
    public void fillTower() {
        for (int i = 0; i < plateNum; i++) {
            stack[i] = plateNum - i;
        }
        top = plateNum - 1;
    }

    // push plate onto current tower
    public void push(int plate) {
        if (stack[0] == 0) {
            top = 0;
            stack[top] = plate;
        } else {
            top+=1;
            stack[top] = plate;
        }
    }

    // pop a plate from current tower
    public int pop() {
        int plate = stack[top];
        stack[top] = 0;
        top--;
        return plate;
    }
}

3.5.MyQueue.java

import java.util.LinkedList;

public class MyQueue<Type> {
    // implement Queue using two stacks represent by LinkedList
    LinkedList<Type> listIn  = new LinkedList<Type>();
    LinkedList<Type> listOut = new LinkedList<Type>();

    public void qPush(Type item) {
        listIn.push(item);
    }

    // Apply lazy loading strategy in pop, so this is a very lazy queue :)
    public Type qPop() {
        if (listOut.isEmpty()) {
            while (listIn.isEmpty() != true) {
                listOut.push(listIn.pop());
            }
        }
        Type item = listOut.pop();
        return item;
    }

    public static void main(String[] args) {
        MyQueue<String> queue = new MyQueue<String>();
        for (String str : args) {
            queue.qPush(str);
            System.out.print(str);
        }
        System.out.println();
        System.out.println(queue.qPop());
        System.out.println(queue.qPop());
    }
}

3.6.SortStack.java

import java.util.LinkedList;

public class SortStack<Type extends Comparable<Type>> {
    LinkedList<Type> stack  = new LinkedList<Type>();
    LinkedList<Type> buffer = new LinkedList<Type>();
    int num;

    public SortStack(Type[] ary) {
        num = ary.length;
        for (Type i : ary) {
            stack.push(i);
        }
    }

    public void sort(){
        // selection sort here
        for (int i = 1 ; i <= num ; i++) {
            // get current min value
            Type min = stack.pop();
            for (int j = num - i - 1; j >= 0; j--) {
                Type item = stack.pop();
                if (min.compareTo(item) < 0) { // min < item
                    buffer.push(min);
                    min = item;
                } else {
                    buffer.push(item);
                }
            }

            // clear buffer
            stack.push(min);
            while (buffer.isEmpty() != true) {
                stack.push(buffer.pop());
            }
        }
    }

    public void print() {
        System.out.println();
        System.out.println(stack.toString());
    }

    public static void main(String[] args) {
        for (String str : args) {
            System.out.print(str+ " ");
        }
        SortStack<String> newStack = new SortStack<String>(args);
        newStack.sort();
        newStack.print();
    }

}

3.7.AnimalShelter.java

import java.util.LinkedList;

class Animal {
    String gerne;
    String name;
    int    index;

    public Animal(String str) {
        name  = str;
    }
}

class Cat extends Animal {

    public Cat(String catName) {
        super(catName);
        gerne = "Cat";
    }
}

class Dog extends Animal {

    public Dog(String dogName) {
        super(dogName);
        gerne = "Dog";
    }
}

public class AnimalShelter {
    // Here we're actually using double linked list
    LinkedList<Animal> dogs = new LinkedList<Animal>();
    LinkedList<Animal> cats = new LinkedList<Animal>();
    int count = 0;

    // enqueue dog and cat in different stack
    public void enqueue(Animal pet) {
        pet.index = count;
        if (pet.gerne == "Dog") {
            dogs.push(pet);
        } else {
            cats.push(pet);
        }
        count++;
    }

    // dequeue the oldest animal (with smallest index)
    public Animal dequeueAny() {
        Animal pet;
        int dogIndex = (dogs.peekFirst() == null ? Integer.MAX_VALUE : dogs.peekFirst().index);
        int catIndex = (cats.peekFirst() == null ? Integer.MAX_VALUE : cats.peekFirst().index);
        if (dogIndex < catIndex) {
            pet = dogs.removeLast();
        } else {
            pet = cats.removeLast();
        }

        return pet;
    }

    // dequeue dog with smallest index
    public Animal dequeueDog() {
        Animal dog = dogs.removeLast();
        return dog;
    }

    // dequeue cat with smallest index
    public Animal dequeueCat() {
        Animal cat = cats.removeLast();
        return cat;
    }

    public static void main(String[] args) {
        AnimalShelter shelter = new AnimalShelter();
        for (String arg : args) {
            Animal tempAnimal = new Dog(arg);
            shelter.enqueue(tempAnimal);
            tempAnimal = new Cat(arg);
            shelter.enqueue(tempAnimal);
            System.out.println(arg + " " + tempAnimal.gerne);
        }

        Animal pet = shelter.dequeueAny();
        System.out.println(pet.name + " " + pet.gerne + " " + pet.index);
        pet = shelter.dequeueDog();
        System.out.println(pet.name + " " + pet.gerne + " " + pet.index);
        pet = shelter.dequeueCat();
        System.out.println(pet.name + " " + pet.gerne + " " + pet.index);
    }
}

4.1.CheckBalance.java

// A very simple binary tree
class Node{
    Node left;
    Node right;
    int data;

    public Node(int d){
        this.data = d;
    }
}

class BinarySearchTree{
    Node root;

    public BinarySearchTree(){
        root = null;
    }

    public void insert(int data){
        root = insert(root, data);
    }

    public Node insert(Node n, int data){
        if (n == null) {
            n = new Node(data);
        } else {
            if (n.data > data) {
                n.left = insert(n.left, data);
            } else {
                n.right = insert(n.right, data);
            }
        }

        return n;
    }

    public int least_common_ancestor(int a, int b){
        return least_common_ancestor(root, a, b);
    }

    private int least_common_ancestor(Node n, int a, int b){
        if (n.data == a || n.data == b) {
            return n.data;
        } else {
            if (Math.abs(a-b) >= n.data) {
                return n.data;
            } else {
                if (a > n.data && b > n.data) {
                    return least_common_ancestor(n.right, a, b);
                } else {
                    return least_common_ancestor(n.left, a, b);
                }
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        for (String s : args) {
            int item = Integer.parseInt(s);
            bst.insert(item);
        }

        System.out.println(bst.least_common_ancestor(1, 2));
    }
}

public class CheckBalance{
    Node root;

    public CheckBalance(BinarySearchTree tree){
        root = tree.root;
    }

    public int height(){
        return height(root);
    }

    private int height(Node t){
        if (t == null) {
            return 0;
        } else {
            return 1 + Math.max(height(t.left), height(t.right));
        }
    }

    public boolean check(){
        return check(root);
    }

    private boolean check(Node t){
        if (t == null) {
            return true;
        } else {
            if (Math.abs(height(t.left) - height(t.right)) >= 2) {
                return false;
            } else {
                return (check(t.left) && check(t.right));
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        for (String s : args) {
            int item = Integer.parseInt(s);
            bst.insert(item);
        }

        CheckBalance c = new CheckBalance(bst);
        System.out.println(c.check());

    }
}

4.2.FindPath.java

import java.util.Hashtable;
import java.util.List;
import java.util.ArrayList;
import java.util.ArrayDeque;

// edges as input
// "2,5"
// "3,1"
// "2,1"
// "4,3"
// "7,9"
// "3,5"
// "6,8"
// "1,6"
// "2,7"
// "3,9"
// output node neighbors relationship
// pay attention to directed or undirected graph

// directed graph
class DNode{
    List<DNode> neighbours = new ArrayList<DNode>(); // nodes pointed to
    String data;

    public DNode(String str){
        data = str;
    }

    public DNode getNeighbour(String str){
        for (int i = 0; i < neighbours.size(); i++){
            if (neighbours.get(i).data == str){
                return neighbours.get(i);
            }
        }
        return null;
    }

    public String getAllNeighbours(){
        String neighbour_data = "";
        for (int i = 0; i < neighbours.size(); i++){
            neighbour_data = neighbour_data + " ";
            neighbour_data = neighbour_data + neighbours.get(i).data;
        }
        return neighbour_data;
    }

    public void addNeighbour(DNode node) {
        neighbours.add(node);
    }
}

class DGraph{
    Hashtable<String, DNode> nodes = new Hashtable<String,DNode>();

    public DGraph(String[] strs){
        for (String str : strs) {
            String[] edge = str.split(",");
            // if graph not contain one or two node of edge, add node to graph
            if (nodes.containsKey(edge[0]) == false){
                addNode(edge[0]);
            }
            if (nodes.containsKey(edge[1]) == false){
                addNode(edge[1]);
            }

            // add edge relation between two nodes
            DNode vertex = nodes.get(edge[0]);
            vertex.addNeighbour(nodes.get(edge[1]));

        }
    }

    public void addNode(String str){
        DNode vertex = new DNode(str);
        nodes.put(str, vertex);
    }

    public static void main(String[] strs){
        String[] str_ary = {"2,5", "3,1", "2,1", "4,3", "7,9", "3,5", "6,8", "1,6", "2,7", "3,9"};
        DGraph dG = new DGraph(str_ary);
        for (String node : dG.nodes.keySet()) {
            System.out.print(dG.nodes.get(node).data + " ");
            System.out.println(dG.nodes.get(node).getAllNeighbours());
        }
    }

}


// Undirected graph
class UdNode{
    UdNode[] neighbours;
    int data;
}

public class FindPath{
    DGraph graph;

    public FindPath(DGraph g) {
        graph = g;
    }

    // BFS is a queue
    public boolean BFS(String a, String b) {
        ArrayDeque<DNode> queue = new ArrayDeque<DNode>();
        queue.addLast(graph.nodes.get(a));
        while(queue.size() != 0){
            DNode currNode = queue.pollFirst();
            if (Integer.parseInt(currNode.data) == Integer.parseInt(b)) {
                return true;
            } else {
                if (graph.nodes.get(currNode.data).neighbours != null){
                    for (DNode node : graph.nodes.get(currNode.data).neighbours){
                        queue.addLast(node);
                    }
                }
            }
        }
        return false;
    }

    // Technically, DFS is a stack, only handle last element first
    public boolean DFS(String a, String b){
        ArrayDeque<DNode> queue = new ArrayDeque<DNode>();
        queue.addLast(graph.nodes.get(a));
        while(queue.size() != 0){
            DNode currNode = queue.pollLast();
            if (Integer.parseInt(currNode.data) == Integer.parseInt(b)) {
                return true;
            } else {
                if (graph.nodes.get(currNode.data).neighbours != null){
                    for (DNode node : graph.nodes.get(currNode.data).neighbours){
                        queue.addLast(node);
                    }
                }
            }
        }
        return false;
    }

    // A recursive way of writing DFS
    public boolean DFSR(String a, String b) {
        if (Integer.parseInt(a) == Integer.parseInt(b)) {
            return true;
        } else{
            for (DNode node : graph.nodes.get(a).neighbours){
                return DFS(node.data, b) || false;
            }
        }
        return false;
    }

    public static void main(String[] strs) {
        String[] str_ary = {"2,5", "3,1", "2,1", "4,3", "7,9", "3,5", "6,8", "1,6", "2,7", "3,9"};
        DGraph dG = new DGraph(str_ary);
        FindPath finder = new FindPath(dG);
        System.out.println(finder.DFS("1", "8"));
        System.out.println(finder.DFSR("4", "3"));
        System.out.println(finder.BFS("2", "9"));

        System.out.println(finder.DFS("1", "7"));
        System.out.println(finder.DFSR("1", "7"));
        System.out.println(finder.BFS("1", "7"));
    }
}

4.3.BST.java

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

class Node{
    int  data;
    Node left;
    Node right;

    public Node(int d){
        data = d;
    }
}

public class BST{
    // get sublist of list don't need to copy the initial array
    // while if use array, you can only copyOfRange to get a part of array
    Node root;

    public BST(List<Integer> ary){
        root = cBST(ary);
    }

    public Node cBST(List<Integer> ary){
        int aryLen = ary.size();
        if (aryLen == 0) {
            return null;
        } else if (aryLen == 1) {
            Node r = new Node(ary.get(0));
            return r;
        } else if (aryLen == 2) {
            Node r = new Node(ary.get(aryLen/2));
            r.left = cBST(ary.subList(0, aryLen/2));
            return r;
        } else {
            Node r = new Node(ary.get(aryLen/2));
            r.left = cBST(ary.subList(0, aryLen/2));
            r.right = cBST(ary.subList(aryLen/2+1, aryLen));
            return r;
        }
    }

    public int height(){
        return height(root);
    }

    private int height(Node r){
        if(r == null){
            return 0;
        } else if(r.left == null && r.right == null) {
            return 0;
        } else {
            return 1 + Math.max(height(r.left), height(r.right));
        }
    }

    public static void main(String[] str){
        ArrayList<Integer> intList = new ArrayList<Integer>();
        for(String s : str){
            intList.add(Integer.parseInt(s));
        }
        BST tree = new BST(intList);
        System.out.println(tree.height());
    }
}

4.4.DepthLinkedList.java

// basic structure of linked list
class Node{
    Node next;
    int  data;

    public Node(int d){
        data = d;
    }
}

// basic structure of binary heap
class BinaryHeap{
    int[] heap = new int[15];
    int last = 0;

    public BinaryHeap(String[] ary){
        for (String s : ary){
            insert(last, Integer.parseInt(s));
            last++;
        }
    }

    public void insert(int addr, int data){
        int parent_addr = (int)Math.ceil(addr/2);
        // System.out.println(parent_addr);
        if (heap[parent_addr] > data){
            heap[addr] = heap[parent_addr];
            heap[parent_addr] = data;
            insert(parent_addr, data);
        } else {
            heap[addr] = data;
        }
    }

    public void printHeap(){
        for (int i : heap){
            System.out.print(i+" ");
        }
        System.out.println();
    }

    public static void main(String[] strs){
        BinaryHeap h = new BinaryHeap(strs);
        h.printHeap();
    }
}

public class DepthLinkedList{
    Node[] listArray;

    public DepthLinkedList(BinaryHeap h){
        // first get the height of tree, this math part is weird...
        int height = (int)(Math.floor((Math.log(h.last)/Math.log(2)) + 1));
        System.out.println(height);
        // initialize nodes array
        listArray = new Node[height];

        // assign head node of each layer in tree to the list array
        for (int i = 0; i < height; i++){
            int start = (int)Math.pow(2, i) - 1;
            int end   = (int)Math.pow(2, i+1) - 1;
            Node head = new Node(h.heap[start]);
            Node temphead = head;
            for (int j = start+1; j < end; j++) {
                Node n = new Node(h.heap[j]);
                temphead.next = n;
                temphead      = temphead.next;
            }
            listArray[i] = head;
        }
    }

    public void printList(){
        for (Node n : listArray){
            // System.out.println(n.data);
            while (n != null){
                System.out.print(n.data + " ");
                n = n.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] strs){
        BinaryHeap h = new BinaryHeap(strs);
        // h.printHeap();
        DepthLinkedList list = new DepthLinkedList(h);
        list.printList();
    }
}