1. 两个有序升序链表S1与S2，合并出S1与S2的并集有序升序链表S3

public class MergeTwoLinkList {
    public static class LinkNode {
        int val;
        LinkNode next;
    }

    // 递归方法 时间复杂度logN
    public static LinkNode MergeTwoLinkList1(LinkNode linkNode1, LinkNode linkNode2) {
        // 递归结束条件
        if (linkNode1 == null)
            return linkNode2;
        if (linkNode2 == null)
            return linkNode1;

        LinkNode head = null;
        if (linkNode1.val <= linkNode2.val) {
            head = linkNode1;
            head.next = MergeTwoLinkList1(linkNode1.next, linkNode2);
        } else {
            head = linkNode2;
            head.next = MergeTwoLinkList1(linkNode1, linkNode2.next);
        }
        return head;
    }

    //遍历方法 时间复杂度n
    public static LinkNode MergeTwoLinkList2(LinkNode linkNode1, LinkNode linkNode2) {
        LinkNode head1 = linkNode1;
        LinkNode head2 = linkNode2;
        LinkNode mergeHead = new LinkNode();
        LinkNode mergePreNode = mergeHead;
        while(head1 != null && head2 != null) {
            LinkNode mergeNode = null;
            if (head1.val <= head2.val) {
                mergeNode = head1;
            } else {
                mergeNode = head2;
            }
            mergePreNode.next = mergeNode;
            mergePreNode = mergeNode;
            head1 = head1.next;
            head2 = head2.next;
        }
        if (linkNode1 == null) {
            mergePreNode = head2;
        }
        if (linkNode2 == null) {
            mergePreNode = head1;
        }
        // 去掉头节点
        mergeHead = mergeHead.next;
        return mergeHead;
    }

    public static void printLinkList(LinkNode head) {
        LinkNode iterator = head;
        while (iterator != null) {
            System.out.println(iterator.val);
            iterator = iterator.next;
        }
        System.out.println("--------------------------------------");
    }

    public static void main(String[] args) {
        // 初始化linklist1
        LinkNode head1 = new LinkNode();
        LinkNode preNode1 = head1;
        for (int i = 1; i <= 10; i++) {
            LinkNode node = new LinkNode();
            node.val = i;
            preNode1.next = node;
            preNode1 = node;
        }
        head1 = head1.next;
        printLinkList(head1);

        // 初始化linklist2
        LinkNode head2 = new LinkNode();
        LinkNode preNode2 = head2;
        for (int i = 5; i <= 12; i++) {
            LinkNode node = new LinkNode();
            node.val = i;
            preNode2.next = node;
            preNode2 = node;
        }
        head2 = head2.next;
        printLinkList(head2);

        LinkNode merge1 = MergeTwoLinkList1(head1, head2);
        printLinkList(merge1);


        LinkNode merge2 = MergeTwoLinkList2(head1, head2);
        printLinkList(merge2);
    }
}

2、判断循环链表

public class CycleLinkList {
    public class LinkNode{
        LinkNode next;
        int val;
    }

    public static boolean isCycleLinkList(LinkNode linkNode) {
        if (linkNode == null) {
            return false;
        }
        // p走一步
        LinkNode p = linkNode;
        // q走两步
        LinkNode q = linkNode;
        while (q == null) {
            p = p.next;
            q = q.next.next;
            if (p == q) {
                return true;
            }
        }
        return false;
    }
}

3、设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个

public class FindLastM {

    public static class LinkNode{
        LinkNode next;
        int val;
    }

    public static int findLastM(LinkNode linkNode, int lastM) {
        LinkNode p = linkNode;
        LinkNode q = linkNode;
        for (int i = 1; i <= lastM; i++) {
            if (q.next != null) {
                q = q.next;
            } else {
                return -1;
            }
        }
        while (q.next != null) {
            p = p.next;
            q = q.next;
        }
        return p.val;
    }

    public static void printLinkList(LinkNode head) {
        LinkNode iterator = head;
        while (iterator != null) {
            System.out.println(iterator.val);
            iterator = iterator.next;
        }
        System.out.println("--------------------------------------");
    }

    public static void main(String[] args) {
        // 初始化linklist
        LinkNode head = new LinkNode();
        LinkNode preNode = head;
        for (int i = 1; i <= 10; i++) {
            LinkNode node = new LinkNode();
            node.val = i;
            preNode.next = node;
            preNode = node;
        }
        head = head.next;
        printLinkList(head);

        System.out.println(findLastM(head, 9));
    }
}

4、二叉树最大深度

public class BinaryTreeDepth {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
    public static int maxDepth(TreeNode treeNode) {
        int depth = 0;
        if (treeNode == null) {
            return depth;
        } else {
            int leftDepth = maxDepth(treeNode.left);
            int rightDepth = maxDepth(treeNode.right);
            if (leftDepth > rightDepth) {
                depth = leftDepth;
            } else {
                depth = rightDepth;
            }
            return depth + 1;
        }
    }
}