Merge Intervals - LeetCode

Merge Intervals

1. sort Intervals
2. compare last interval in result with current Interval.

Two Sum - LeetCode

Two Sum

Using HashMap to solve this problem would be much easier.

String to Integer (atoi) - LeetCode

String to Integer (atoi)

Watch out the corner cases. 

Climbing Stairs - LeetCode

Climbing Stairs

1. Recursive:
We can use recursive way to solve this problem: O(n) = O(n - 1) + O(n - 2).

2. DP:
This method also very straightforward. dp[i] means how many ways to reach level i. So it would take O(n) time and O(n) space to solve the problem.

3. Two pointers:
We also can use to pointers to store the info. It is like DP. But the space is reduced to O(1).

Validate Binary Search Tree - LeetCode

Validate Binary Search Tree

This problem is like the other tree questions, recursive method is the easiest read way.

Here is the code:

Pow(x, n) - LeetCode

Pow(x, n)

This question is very easy. But the corner case must be considered in.

1. negative n.
2. n equals to 0.

Then we can using recursive method to solve this problem.

Here is the code: 
Additional throughout: how about n is also double?

Word Ladder - LeetCode

Word Ladder

For this problem, BFS is better than DFS. 

DFS, it's like from the first char to the last char of the word, try to match the dictionary. However, if there is not match, then start from last matching char and do the same again. So it is not efficiency. 

Using BFS, it is like Level traverse a tree. So it would reduce the times for matching. 

Here is the code. Using two queue( the distance Queue is not required. it just used for store the distance every time generate.) to do the BFS. (when mention the BFS, the first thought must be Queue. LOL).

About BFS

Here is the problems solved by using BFS on LeetCode OJ.

package InterviewCode;

import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

import java.util.Set;

import java.util.Stack;

import Util.TreeNode;

public class AboutBFS

{

    //Binary Tree Level Order Traversal 

    public List> levelOrder(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        Queue queue = new LinkedList();

        queue.add(root);

        int curNodeNum = 1;

        int nextNodeNum = 0;

        ArrayList array = new ArrayList();

        while (!queue.isEmpty())

        {

            TreeNode node = queue.poll();

            array.add(node.val);

            if (node.left != null)

            {

                queue.add(node.left);

                nextNodeNum++;

            }

            if (node.right != null)

            {

                queue.add(node.right);

                nextNodeNum++;

            }

            curNodeNum--;

            if (curNodeNum == 0)

            {

                result.add(new ArrayList(array));

                array.clear();

                curNodeNum = nextNodeNum;

                nextNodeNum = 0;

            }

        }

        return result;

    }

    //Binary Tree Level Order Traversal II 

    public List> levelOrderII(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        Queue queue = new LinkedList();

        Stack> stack = new Stack>();

        queue.add(root);

        int curNodeNum = 1;

        int nextNodeNum = 0;

        ArrayList array = new ArrayList();

        while (!queue.isEmpty())

        {

            TreeNode node = queue.poll();

            array.add(node.val);

            if (node.left != null)

            {

                queue.add(node.left);

                nextNodeNum++;

            }

            if (node.right != null)

            {

                queue.add(node.right);

                nextNodeNum++;

            }

            curNodeNum--;

            if (curNodeNum == 0)

            {

                stack.push(new ArrayList(array));

                array.clear();

                curNodeNum = nextNodeNum;

                nextNodeNum = 0;

            }

        }

        while (!stack.isEmpty())

        {

            result.add(stack.pop());

        }

        return result;

    }

    //Surrounded Regions

    public void solve(char[][] board)

    {

        if (board.length == 0 || board[0].length == 0)

        {

            return;

        }

        Queue rowQueue = new LinkedList();

        Queue colQueue = new LinkedList();

        for (int row = 0; row < board.length; row++)

        {

            if (board[row][0] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(0);

            }

            if (board[row][board[0].length - 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(board[0].length - 1);

            }

        }

        for (int col = 1; col <= board[0].length - 2; col++)

        {

            if (board[0][col] == 'O')

            {

                rowQueue.offer(0);

                colQueue.offer(col);

            }

            if (board[board.length - 1][col] == 'O')

            {

                rowQueue.offer(board.length - 1);

                colQueue.offer(col);

            }

        }

        while (!rowQueue.isEmpty())

        {

            int row = rowQueue.poll();

            int col = colQueue.poll();

            board[row][col] = 'Y';

            if (row >= 1 && board[row - 1][col] == 'O')

            {

                rowQueue.offer(row - 1);

                colQueue.offer(col);

            }

            if (row <= board.length - 2 && board[row + 1][col] == 'O')

            {

                rowQueue.offer(row + 1);

                colQueue.offer(col);

            }

            if (col >= 1 && board[row][col - 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(col - 1);

            }

            if (col <= board[0].length - 2 && board[row][col + 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(col + 1);

            }

        }

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

        {

            for (int j = 0; j < board[0].length; j++)

            {

                if (board[i][j] == 'Y')

                {

                    board[i][j] = 'O';

                }

                else if (board[i][j] == 'O')

                {

                    board[i][j] = 'X';

                }

            }

        }

    }

    //Word Ladder

    public int ladderLength(String start, String end, Set dict)

    {

        if (start.length() != end.length() || dict.size() == 0)

        {

            return 0;

        }

        Queue wordQueue = new LinkedList();

        Queue disQueue = new LinkedList();

        wordQueue.offer(start);

        disQueue.offer(1);

        while (!wordQueue.isEmpty())

        {

            String s = wordQueue.poll();

            int dis = disQueue.poll();

            if (s.equals(end))

            {

                return dis;

            }

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

            {

                char[] chars = s.toCharArray();

                for (char j = 'a'; j <= 'z'; j++)

                {

                    chars[i] = j;

                    String newword = new String(chars);

                    if (dict.contains(newword))

                    {

                        wordQueue.offer(newword);

                        disQueue.offer(dis + 1);

                        dict.remove(newword);

                    }

                }

            }

        }

        return 0;

    }

    //Binary Tree Zigzag Level Order Traversal 

    public List> zigzagLevelOrder(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        ArrayList arrayList = new ArrayList();

        Queue queue = new LinkedList();

        queue.add(root);

        int num = 0;

        boolean reversed = false;

        while (!queue.isEmpty())

        {

            num = queue.size();

            arrayList.clear();

            for (int i = 0; i < num; i++)

            {

                TreeNode node = queue.remove();

                arrayList.add(node.val);

                if (node.left != null)

                {

                    queue.add(node.left);

                }

                if (node.right != null)

                {

                    queue.add(node.right);

                }

            }

            if (reversed)

            {

                Collections.reverse(arrayList);

                reversed = false;

            }

            else

            {

                reversed = true;

            }

            result.add(new ArrayList(arrayList));

        }

        return result;

    }

}

About DFS

Here is all the problems using DFS solved on LeetCode OJ.

package InterviewCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

import Util.TreeNode;

public class AboutDFS
{
    //Letter Combinations of a Phone Number
    public List letterCombinations(String digits)
    {
        HashMap map = new HashMap();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        ArrayList result = new ArrayList();
        char[] chars = new char[digits.length()];
        dfs(digits, 0, result, chars, map);
        return result;
    }

    private void dfs(String digits, int index, ArrayList result, char[] chars, HashMap map)
    {
        if (index == digits.length())
        {
            result.add(new String(chars));
        }
        String letters = map.get(digits.charAt(index));
        for (int i = 0; i < letters.length(); i++)
        {
            chars[index] = letters.charAt(i);
            dfs(digits, index + 1, result, chars, map);
        }
    }

    //Generate Parentheses
    public List generateParenthesis(int n)
    {
        ArrayList result = new ArrayList();
        if (n <= 0)
        {
            return result;
        }
        String s = new String();
        dfs(n, n, s, result);
        return result;
    }

    private void dfs(int l, int r, String s, ArrayList result)
    {
        if (r < l)
        {
            return;
        }
        if (l == 0 && r == 0)
        {
            result.add(s);
        }
        if (l >= 1)
        {
            dfs(l - 1, r, s + "(", result);
        }
        if (r >= 1)
        {
            dfs(l, r - 1, s + ")", result);
        }
    }

    //Sudoku Solver
    public void solveSudoku(char[][] board)
    {
        dfs(board, 0, 0);
    }

    private boolean dfs(char[][] board, int i, int j)
    {
        if (j >= 9)
        {
            return dfs(board, i + 1, 0);
        }
        if (i == 9)
        {
            return true;
        }
        if (board[i][j] == '.')
        {
            for (int k = 1; k <= 9; k++)
            {
                board[i][j] = (char) (k + '0');
                if (isValid(board, i, j))
                {
                    if (dfs(board, i, j + 1))
                    {
                        return true;
                    }
                }
                board[i][j] = '.';
            }
        }
        else
        {
            return dfs(board, i, j + 1);
        }
        return false;
    }

    private boolean isValid(char[][] board, int i, int j)
    {
        for (int k = 0; k < 9; k++)
        {
            if (k != j && board[i][k] == board[i][j])
                return false;
        }
        for (int k = 0; k < 9; k++)
        {
            if (k != i && board[k][j] == board[i][j])
                return false;
        }
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
        {
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
            {
                if ((row != i || col != j) && board[row][col] == board[i][j])
                    return false;
            }
        }
        return true;
    }

    //N-Queens
    public List solveNQueens(int n)
    {
        ArrayList result = new ArrayList();
        if (n <= 0)
        {
            return result;
        }
        String[] rows = new String[n];
        dfs(0, n, rows, result);
        return result;
    }

    private void dfs(int row, int n, String[] rows, ArrayList result)
    {
        if (row >= n)
        {
            result.add(rows.clone());
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!isValid(col, row, rows))
            {
                continue;
            }

            char[] chars = new char[n];
            Arrays.fill(chars, '.');
            chars[col] = 'Q';

            rows[row] = String.valueOf(chars);
            dfs(row + 1, n, rows, result);
        }
    }

    private boolean isValid(int col, int row, String[] rows)
    {
        for (int i = 0; i < row; i++)
        {
            int indexQ = rows[i].indexOf('Q');
            if (indexQ == col)
            {
                return false;
            }

            int rowDis = Math.abs(row - i);
            int colDis = Math.abs(col - indexQ);
            if (rowDis == colDis)
            {
                return false;
            }
        }
        return true;
    }

    //N-Queens II
    public int totalNQueens(int n)
    {
        int[] result = new int[1];
        if (n <= 0)
        {
            return result[0];
        }
        String[] rows = new String[n];
        dfs(0, n, rows, result);
        return result[0];
    }

    private void dfs(int row, int n, String[] rows, int[] result)
    {
        if (row >= n)
        {
            result[0] += 1;
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!isValid(col, row, rows))
            {
                continue;
            }

            char[] chars = new char[n];
            Arrays.fill(chars, '.');
            chars[col] = 'Q';

            rows[row] = String.valueOf(chars);
            dfs(row + 1, n, rows, result);
        }
    }

    //Word Search
    public boolean exist(char[][] board, String word)
    {
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (dfs(board, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j)
    {
        if (index == word.length() - 1 && word.charAt(word.length() - 1) == board[i][j])
        {
            return true;
        }
        if (word.charAt(index) != board[i][j])
        {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = '.';
        boolean b1 = false, b2 = false, b3 = false, b4 = false;
        if (i - 1 >= 0 && board[i - 1][j] != '.')
        {
            b1 = dfs(board, word, index + 1, i - 1, j);
        }
        if (!b1 && j - 1 >= 0 && board[i][j - 1] != '.')
        {
            b2 = dfs(board, word, index + 1, i, j - 1);
        }
        if (!b1 && !b2 && i + 1 < board.length && board[i + 1][j] != '.')
        {
            b3 = dfs(board, word, index + 1, i + 1, j);
        }
        if (!b1 && !b2 && b3 && j + 1 < board[0].length && board[i][j + 1] != '.')
        {
            b4 = dfs(board, word, index + 1, i, j + 1);
        }
        board[i][j] = temp;
        return b1 || b2 || b3 || b4;
    }

    //Restore IP Addresses
    public List restoreIpAddresses(String s)
    {
        ArrayList result = new ArrayList();
        if (s.length() < 4 || s.length() > 12)
        {
            return result;
        }
        dfs(s, "", result, 0);
        return result;
    }

    private void dfs(String s, String tmp, ArrayList result, int count)
    {
        if (count == 3 && isValidIP(s))
        {
            result.add(tmp + s);
            return;
        }
        for (int i = 1; i < 4 && i < s.length(); i++)
        {
            String substr = s.substring(0, i);
            if (isValidIP(substr))
            {
                dfs(s.substring(i), tmp + substr + '.', result, count + 1);
            }
        }
    }

    private boolean isValidIP(String s)
    {
        if (s.charAt(0) == '0')
        {
            return s.equals("0");
        }
        int num = Integer.parseInt(s);
        return num <= 255 && num > 0;
    }

    //Validate Binary Search Tree
    public boolean isValidBST(TreeNode root)
    {
        return isValidate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isValidate(TreeNode root, int min, int max)
    {
        if (root == null)
        {
            return true;
        }
        if (min >= root.val || max <= root.val)
        {
            return false;
        }
        return isValidate(root.left, min, root.val) && isValidate(root.right, root.val, max);
    }

    // Recover Binary Search Tree
    TreeNode pre;
    TreeNode first;
    TreeNode second;

    private void inorder(TreeNode root)
    {
        if (root == null)
            return;
        inorder(root.left);
        if (pre == null)
        {
            pre = root;
        }
        else
        {
            if (pre.val > root.val)
            {
                if (first == null)
                {
                    first = pre;
                }
                second = root;
            }
            pre = root;
        }
        inorder(root.right);
    }

    public void recoverTree(TreeNode root)
    {
        pre = null;
        first = null;
        second = null;
        inorder(root);
        if (first != null && second != null)
        {
            int tem = first.val;
            first.val = second.val;
            second.val = tem;
        }
    }

    //Same Tree
    public boolean isSameTree(TreeNode p, TreeNode q)
    {
        if (p == null)
        {
            return q == null;
        }
        if (q == null)
        {
            return p == null;
        }
        if (p.val != q.val)
        {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //Symmetric Tree
    public boolean isSymmetric(TreeNode root)
    {
        if (root == null)
        {
            return true;
        }

        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right)
    {
        if (left == null)
        {
            return right == null;
        }
        if (right == null)
        {
            return left == null;
        }
        if (left.val != right.val)
        {
            return false;
        }
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }

    //Construct Binary Tree from Preorder and Inorder Traversal
    public TreeNode buildTree(int[] preorder, int[] inorder)
    {
        int preLen = preorder.length;
        int inLen = inorder.length;
        return dfs(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
    }

    private TreeNode dfs(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd)
    {
        if (preStart > preEnd)
        {
            return null;
        }

        int rootVal = preorder[preStart];
        int rootIndex = 0;

        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder[i] == rootVal)
            {
                rootIndex = i;
                break;
            }
        }

        int len = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = dfs(preorder, preStart + 1, preStart + len, inorder, inStart, rootIndex - 1);
        root.right = dfs(preorder, preStart + len + 1, preEnd, inorder, rootIndex + 1, inEnd);

        return root;
    }

    //Convert Sorted Array to Binary Search Tree
    public TreeNode sortedArrayToBST(int[] num)
    {
        if (num == null || num.length == 0)
        {
            return null;
        }
        return dfs(num, 0, num.length - 1);
    }

    private TreeNode dfs(int[] num, int start, int end)
    {
        if (start > end)
        {
            return null;
        }
        int mid = (end - start) / 2 + start;
        TreeNode root = new TreeNode(num[mid]);
        root.left = dfs(num, start, mid - 1);
        root.right = dfs(num, mid + 1, end);
        return root;
    }

    //Balanced Binary Tree
    public boolean isBalanced(TreeNode root)
    {
        if (root == null)
        {
            return true;
        }
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1)
        {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int getDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        return 1 + Math.max(getDepth(root.left), getDepth(root.right));
    }

    //Minimum Depth of Binary Tree
    public int minDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        int a = minDepth(root.left);
        int b = minDepth(root.right);
        if (a * b != 0)
        {
            return Math.min(a, b) + 1;
        }
        else if (a == 0)
        {
            return b + 1;
        }
        else
        {
            return a + 1;
        }
    }

    //Path Sum
    public boolean hasPathSum(TreeNode root, int sum)
    {
        if (root == null)
        {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum)
        {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    //Populating Next Right Pointers in Each Node
    public class TreeLinkNode
    {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x)
        {
            val = x;
        }
    }

    public void connect(TreeLinkNode root)
    {
        if (root == null)
        {
            return;
        }
        if (root.left != null)
        {
            root.left.next = root.right;
        }
        if (root.right != null && root.next != null)
        {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }

    //Populating Next Right Pointers in Each Node II
    public void connectII(TreeLinkNode root)
    {
        if (root == null)
        {
            return;
        }
        TreeLinkNode rootNext = root.next;
        TreeLinkNode next = null;
        while (rootNext != null)
        {
            if (rootNext.left != null)
            {
                next = rootNext.left;
                break;
            }
            else if (rootNext.right != null)
            {
                next = rootNext.right;
                break;
            }
            else
            {
                rootNext = rootNext.next;
            }
        }
        if (root.left != null)
        {
            if (root.right != null)
            {
                root.left.next = root.right;
            }
            else
            {
                root.left.next = next;
            }
        }
        if (root.right != null)
        {
            root.right.next = next;
        }
        //!!!! right first!!!
        connect(root.right);
        connect(root.left);
    }

    //Binary Tree Maximum Path Sum
    public int maxPathSum(TreeNode root)
    {
        int[] max = { Integer.MIN_VALUE };
        dfs(root, max);
        return max[0];
    }

    private int dfs(TreeNode root, int[] max)
    {
        if (root == null)
        {
            return 0;
        }
        int leftSubMaxSum = dfs(root.left, max);
        int rightSubMaxSum = dfs(root.right, max);
        int arch = leftSubMaxSum + root.val + rightSubMaxSum;

        int maxPathAcrossRootToParent = Math.max(root.val, Math.max(leftSubMaxSum, rightSubMaxSum) + root.val);
        max[0] = Math.max(max[0], Math.max(arch, maxPathAcrossRootToParent));
        return maxPathAcrossRootToParent;
    }

    //Sum Root to Leaf Numbers
    public int sumNumbers(TreeNode root)
    {
        int[] result = { 0 };
        int current = 0;
        dfs(root, current, result);
        return result[0];
    }

    private void dfs(TreeNode root, int current, int[] result)
    {
        if (root == null)
        {
            return;
        }
        current = current * 10 + root.val;
        if (root.left == null && root.right == null)
        {
            result[0] += current;
            return;
        }
        dfs(root.left, current, result);
        dfs(root.right, current, result);
    }

    //Palindrome Partitioning
    public List> partition(String s)
    {
        ArrayList> result = new ArrayList>();
        if (s == null || s.length() == 0)
        {
            return result;
        }
        ArrayList array = new ArrayList();
        HashMap map = new HashMap();
        dfs(s, 0, map, result, array);
        return result;
    }

    private void dfs(String s, int index, HashMap map, ArrayList> result, ArrayList array)
    {
        if (index == s.length())
        {
            result.add(new ArrayList(array));
            return;
        }
        for (int i = index; i < s.length(); i++)
        {
            boolean isPalindrome = false;
            String subString = s.substring(index, i + 1);
            if (map.get(subString) != null)
            {
                isPalindrome = map.get(subString);
            }
            else
            {
                isPalindrome = checkIsPalindrome(subString);
                map.put(subString, isPalindrome);
            }
            if (isPalindrome)
            {
                array.add(subString);
                dfs(s, i + 1, map, result, array);
                //TODO: why remove last???
                array.remove(array.size() - 1);
            }
        }
    }

    private boolean checkIsPalindrome(String s)
    {
        int i = 0;
        int j = s.length() - 1;
        while (i < j)
        {
            if (s.charAt(i) != s.charAt(j))
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

About List interview questions

List is  one of the most popular code interview topic. Here is some basic List interview questions. Wish it would help you success in interviewing.

package InterviewCode;

import java.util.HashMap;

import java.util.Stack;

import Util.ListNode;

/**

 * @author jwang

 *

 * 1. get list length

 * 2. reverse a list (iterative, recursive)

 * 3. find the kth element count backwards (iterative, recursive)

 * 4. find the middle element

 * 5. reversely print the list (iterative, recursive)

 * 6. merge two sorted lists (iterative, recursive)

 * 7. detect whether a list has cycle

 * 8. detect whether two lists intersect

 * 9. get first common node from two lists

 * 10. find the first node in the cycle list (two ways)

 * 11. delete a node in O(n)

 */

public class AboutList

{

    //1. get list length

    public int getLength(ListNode head)

    {

        if (head == null)

            return 0;

        ListNode cur = head;

        int counter = 0;

        while (cur != null)

        {

            counter++;

            cur = cur.next;

        }

        return counter;

    }

    //2. reverse a list (iterative) -- not broke the original list

    public ListNode reverseList(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode newHead = null;

        ListNode cur = head;

        while (cur != null)

        {

            ListNode preCur = cur;

            cur = cur.next;

            preCur.next = newHead;

            newHead = preCur;

        }

        return newHead;

    }

    //2. reverse a list (iterative) -- broke the orignal list

    public ListNode reverseListBr(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode cur = head;

        ListNode post = cur.next;

        while (post != null)

        {

            ListNode tem = post.next;

            post.next = cur;

            cur = post;

            post = tem;

        }

        return cur;

    }

    //2. reverse a list (recursive)

    public ListNode reverseListRec(ListNode head)

    {

        if (head == null || head.next == null)

            return head;

        ListNode newHead = reverseListRec(head.next);

        head.next.next = head;

        head.next = null;

        return newHead;

    }

    //3. find the kth element count backwards (iterative)

    public ListNode findKBackwards(ListNode head, int k)

    {

        if (head == null || k == 0)

        {

            return null;

        }

        ListNode fast = head;

        ListNode slow = head;

        while (k > 1 && fast != null)

        {

            fast = fast.next;

            k--;

        }

        if (k > 1 || fast == null)

        {

            return null;

        }

        while (fast != null)

        {

            fast = fast.next;

            slow = slow.next;

        }

        return slow;

    }

    private int counter = 0;

    //3. find the kth element count backwards (recursive)

    public ListNode findBackwardsRec(ListNode head, int k)

    {

        if (head == null && k == 0)

            return null;

        findBackwardsRec(head.next, k);

        counter++;

        if (counter == k)

        {

            return head;

        }

        return null;

    }

    //4. find the middle element

    public ListNode findMidNode(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode fast = head;

        ListNode slow = head;

        while (fast != null)

        {

            slow = slow.next;

            fast = fast.next;

            if (fast.next != null)

            {

                fast = fast.next;

            }

        }

        return slow;

    }

    //5. reversely print the list (iterative)

    public void printListReversely(ListNode head)

    {

        if (head == null)

            return;

        Stack<ListNode> stack = new Stack<ListNode>();

        while (head != null)

        {

            stack.push(head);

            head = head.next;

        }

        ListNode listNode = null;

        while (!stack.isEmpty())

        {

            listNode = stack.pop();

            System.out.println(listNode.val);

        }

    }

    //5. reversely print the list (recursive)

    public void printListReverselyRec(ListNode head)

    {

        if (head == null)

        {

            return;

        }

        printListReverselyRec(head.next);

        System.out.println(head.val);

    }

    //6. merge two sorted lists (iterative)

    public ListNode mergeTwoList(ListNode head1, ListNode head2)

    {

        if (head1 == null)

        {

            return head2;

        }

        if (head2 == null)

        {

            return head1;

        }

        ListNode result = null;

        if (head1.val > head2.val)

        {

            result = head2;

            head2 = head2.next;

        }

        else

        {

            result = head1;

            head1 = head1.next;

        }

        while (head1 != null && head2 != null)

        {

            if (head1.val > head2.val)

            {

                result.next = head2;

                head2 = head2.next;

                result = result.next;

            }

            else

            {

                result.next = head1;

                head1 = head1.next;

                result = result.next;

            }

        }

        if (head1 != null)

        {

            result.next = head1;

        }

        else if (head2 != null)

        {

            result.next = head2;

        }

        return result;

    }

    //6. merge two sorted lists (iterative)

    public ListNode mergeTwoListRec(ListNode head1, ListNode head2)

    {

        if (head1 == null)

        {

            return head2;

        }

        if (head2 == null)

        {

            return head1;

        }

        ListNode result = null;

        if (head1.val > head2.val)

        {

            result = head2;

            result.next = mergeTwoListRec(head1, head2.next);

        }

        else

        {

            result = head1;

            result.next = mergeTwoListRec(head1.next, head2);

        }

        return result;

    }

    //7. detect whether a list has cycle

    public boolean hasCycle(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return false;

        }

        ListNode fast = head;

        ListNode slow = head;

        while (fast != null && fast.next != null)

        {

            fast = fast.next.next;

            slow = slow.next;

            if (fast == slow)

                return true;

        }

        return false;

    }

    //8. detect whether two lists intersect

    public boolean hasIntersect(ListNode head1, ListNode head2)

    {

        if (head1 == null || head2 == null)

        {

            return false;

        }

        while (head1 != null)

            head1 = head1.next;

        while (head2 != null)

            head2 = head2.next;

        return head1 == head2;

    }

    //9. get first common node from two lists

    public ListNode getFirstCommonNode(ListNode head1, ListNode head2)

    {

        if (head1 == null || head2 == null)

            return null;

        //get length 

        int len1 = 1;

        ListNode temp1 = head1;

        while (temp1.next != null)

        {

            temp1 = temp1.next;

            len1++;

        }

        int len2 = 1;

        ListNode temp2 = head2;

        while (temp2.next != null)

        {

            temp2 = temp2.next;

            len2++;

        }

        if (temp1 != temp2)

            return null;

        ListNode list1 = head1;

        ListNode list2 = head2;

        if (len1 > len2)

        {

            int offset = len1 - len2;

            while (offset > 0)

            {

                offset--;

                list1 = list1.next;

            }

        }

        else

        {

            int offset = len2 - len1;

            while (offset > 0)

            {

                offset--;

                list2 = list2.next;

            }

        }

        while (list1 != list2)

        {

            list1 = list1.next;

            list2 = list2.next;

        }

        return list1;

    }

    //10. find the first node in the cycle list (fast-slow pointer way)

    public ListNode findFristNodeInCycleList(ListNode head)

    {

        ListNode fast = head;

        ListNode slow = head;

        while (fast != null && fast.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast)

            {

                break;

            }

        }

        if (fast == null || fast.next == null)

        {

            return null;

        }

        slow = head;

        while (slow != fast)

        {

            slow = slow.next;

            fast = fast.next;

        }

        return fast;

    }

    //10. find the first node in the cycle list (hash map way)

    public ListNode findFirstNodeInCycleListHash(ListNode head)

    {

        HashMap<ListNode, Boolean> hashMap = new HashMap<ListNode, Boolean>();

        while (head != null)

        {

            if (hashMap.get(head) == true)

            {

                return head;

            }

            else

            {

                hashMap.put(head, true);

                head = head.next;

            }

        }

        return null;

    }

    //11. delete a node in O(n)

    public void deleteListNode(ListNode head, ListNode delete)

    {

        if (delete == null)

            return;

        if (delete.next != null)

        {

            delete.val = delete.next.val;

            delete.next = delete.next.next;

        }

        else

        {

            if (head == delete)

                head = null;

            else

            {

                ListNode tem = head;

                while (tem.next != delete)

                {

                    tem = tem.next;

                }

                tem.next = null;

            }

        }

    }

    //12. sort list

    public ListNode sortList(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode fast = head;

        ListNode slow = head;

        while (fast.next != null && fast.next.next != null)

        {

            fast = fast.next.next;

            slow = slow.next;

        }

        fast = slow.next;

        slow.next = null;

        slow = sortList(head);

        fast = sortList(fast);

        return merge(slow, fast);

    }

    private ListNode merge(ListNode slow, ListNode fast)

    {

        ListNode head = new ListNode(0);

        ListNode cur = head;

        while (slow != null && fast != null)

        {

            if (slow.val <= fast.val)

            {

                cur.next = slow;

                slow = slow.next;

            }

            else

            {

                cur.next = fast;

                fast = fast.next;

            }

            cur = cur.next;

        }

        if (slow != null)

        {

            cur.next = slow;

        }

        if (fast != null)

        {

            cur.next = fast;

        }

        return head.next;

    }

    //insersion sort list

    public ListNode insertionSortList(ListNode head)

    {

        ListNode newHead = new ListNode(0);

        ListNode helper = newHead;

        ListNode cur = head;

        while (cur != null)

        {

            ListNode next = cur.next;

            helper = newHead;

            while (helper.next != null && helper.next.val < cur.val)

            {

                helper = helper.next;

            }

            cur.next = helper.next;

            helper.next = cur;

            cur = next;

        }

        return newHead.next;

    }

    //reorder list

    public void reorderList(ListNode head)

    {

        if (head == null || head.next == null || head.next.next == null)

        {

            return;

        }

        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null)

        {

            fast = fast.next.next;

            slow = slow.next;

        }

        //reverse the list

        ListNode head1 = head;

        ListNode head2 = slow.next;

        slow.next = null;

        ListNode cur = head2, post = cur.next;

        cur.next = null;

        while (post != null)

        {

            ListNode tem = post.next;

            post.next = cur;

            cur = post;

            post = tem;

        }

        head2 = cur;

        //merge

        ListNode a = head1;

        ListNode b = head2;

        while (b != null)

        {

            ListNode tem1 = a.next;

            ListNode tem2 = b.next;

            a.next = b;

            b.next = tem1;

            a = tem1;

            b = tem2;

        }

    }

    //Reverse Linked List II 

    public ListNode reverseBetween(ListNode head, int m, int n)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode pre = dummy, cur = null, post = null;

        for (int i = 1; i <= n; i++)

        {

            if (i < m)

            {

                pre = pre.next;

            }

            else if (i == m)

            {

                cur = pre.next;

                post = cur.next;

            }

            else

            {

                cur.next = post.next;

                post.next = pre.next;

                pre.next = post;

                post = cur.next;

            }

        }

        return dummy.next;

    }

    //Partition List

    public ListNode partition(ListNode head, int x)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode pre = new ListNode(0);

        ListNode post = new ListNode(0);

        ListNode cur = head, tem1 = pre, tem2 = post;

        while (cur != null)

        {

            if (cur.val < x)

            {

                pre.next = new ListNode(cur.val);

                pre = pre.next;

            }

            else

            {

                post.next = new ListNode(cur.val);

                post = post.next;

            }

            cur = cur.next;

        }

        if (pre != null)

        {

            pre.next = tem2.next;

        }

        return tem1.next;

    }

    //Remove Duplicates from Sorted List 

    public ListNode deleteDuplicates(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode pre = head;

        ListNode cur = head.next;

        while (cur != null)

        {

            if (cur.val == pre.val)

            {

                pre.next = cur.next;

                cur = cur.next;

            }

            else

            {

                pre = cur;

                cur = cur.next;

            }

        }

        return head;

    }

    //Remove Duplicates from Sorted List II

    public ListNode deleteDuplicatesII(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode cur = dummy;

        while (cur.next != null)

        {

            ListNode post = cur.next;

            while (post.next != null && post.next.val == post.val)

            {

                post = post.next;

            }

            if (post != cur.next)

            {

                cur.next = post.next;

            }

            else

            {

                cur = cur.next;

            }

        }

        return dummy.next;

    }

    //Merge Two Sorted Lists

    public ListNode mergeTwoLists(ListNode l1, ListNode l2)

    {

        if (l1 == null)

        {

            return l2;

        }

        if (l2 == null)

        {

            return l1;

        }

        ListNode newHead = new ListNode(0);

        ListNode cur = newHead;

        while (l1 != null && l2 != null)

        {

            if (l1.val <= l2.val)

            {

                cur.next = new ListNode(l1.val);

                l1 = l1.next;

            }

            else

            {

                cur.next = new ListNode(l2.val);

                l2 = l2.next;

            }

            cur = cur.next;

        }

        if (l1 != null)

        {

            cur.next = l1;

        }

        if (l2 != null)

        {

            cur.next = l2;

        }

        return newHead.next;

    }

    //Rotate List 

    public ListNode rotateRight(ListNode head, int n)

    {

        if (head == null || n == 0)

            return head;

        ListNode p = head;

        int len = 1;//since p is already point to head

        while (p.next != null)

        {

            len++;

            p = p.next;

        }

        p.next = head; //form a loop

        n = n % len;

        for (int i = 0; i < len - n; i++)

        {

            p = p.next;

        } //now p points to the prev of the new head

        head = p.next;

        p.next = null;

        return head;

    }

    //Remove Nth Node From End of List

    public ListNode removeNthFromEnd(ListNode head, int n)

    {

        ListNode fast = head;

        ListNode slow = head;

        for (int i = 0; i < n; i++)

        {

            fast = fast.next;

        }

        if (fast == null)

        {

            head = head.next;

            return head;

        }

        while (fast.next != null)

        {

            fast = fast.next;

            slow = slow.next;

        }

        slow.next = slow.next.next;

        return head;

    }

}