剑指offer 15~17

15.反转链表
输入一个链表，反转链表后，输出链表的所有元素。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode tmp1,tmp2,tmp3;
        tmp1 =head;
        
        if(tmp1.next!=null){
            tmp2 = tmp1.next;
            tmp1.next =null;
        }else{
            return tmp1;
        }
        
        while(tmp2.next!=null){
            tmp3 = tmp2.next;
            tmp2.next = tmp1;
            
            tmp1=tmp2;
            tmp2=tmp3;
        }
        tmp2.next = tmp1;
        
        return tmp2;
    }
}

16.合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }
        //确定谁为主
        ListNode primary;
        ListNode secondary;
        if(list1.val <= list2.val){
            primary = list1;
            secondary = list2;
        }else{
            primary = list2;
            secondary = list1;
        }
        //记录头节点
        list1 = primary;list2 = secondary;
        
        while(secondary!=null){
            //如果当前位置比较小
            if(primary.val <= secondary.val){
                if(primary.next==null){
                    primary.next = secondary;
                    return list1;
                }else{
                    ListNode next = primary.next;
                    primary.next = secondary;
                    
                    while(secondary.next!=null && secondary.next.val < next.val){
                        //如果下一个依然大于 主链表的下一个
                        secondary = secondary.next;
                    }
                    ListNode secondaryNext =secondary.next;
                    secondary.next = next;
                    primary=next;
                    secondary =secondaryNext;
                }
                
            }else{
                if(primary.next!=null){
                    primary = primary.next;
                }else{
                    primary.next = secondary;
                    return list1;
                }
                
            }
        }
        return list1;
    }
}

17.树的子结构
输入两颗二叉树A，B，判断B是不是A的子结构。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        
        if(root2==null){
            return false;
        }else if(root1==null){
            return false;
        }
        
        if(root1.val==root2.val){
            if(compare(root1,root2)){
                return true;
            }
        }
        if(HasSubtree(root1.left, root2))return true;
        if(HasSubtree(root1.right, root2))return true ;
        
        return false;
        
    }
    public boolean compare(TreeNode root1 ,TreeNode root2){
       if(root2==null){
            return true;
        }else if(root1==null && root2!=null){
           return false;
       }else if(root1.val == root2.val){
            if(compare(root1.left,root2.left) && compare(root1.right,root2.right)){
                return true;
            }
        }
        
        return false;
        
    }
    
}

#一些为了检测写的函数
    
    public static void main(String[] args) {
        int[] array1={8,8,7,9,3,-1,-1,-1,-1,4,7};
        TreeNode head1 = create(array1);

        int[] array2 ={8,9,2};
        TreeNode head2 = create(array2);
//        travel(head1);
        System.out.println(HasSubtree(head1, head2));
    }
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    public static void travel(TreeNode tree){
        ArrayList<TreeNode> trees = new ArrayList<TreeNode>();
        trees.add(tree);
        TreeNode last =tree;
        int count=0;
        int size =1;
        int empty=0;
        while(!trees.isEmpty()){
            tree = trees.remove(0);
            if(tree==null){
                trees.add(null);
                trees.add(null);
            }else {
                trees.add(tree.left);
                trees.add(tree.right);
            }
            if(tree!=null) {
                System.out.print(tree.val);
            }else{
                System.out.print( " ");
                empty++;
            }
            count++;
            if(count==size){
                System.out.println();
                size=size*2;
                if(empty==count){
                    break;
                }
                count =0;
                empty=0;

            }
        }
    }

    public static TreeNode create(int[] array){
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        TreeNode first = new TreeNode(array[0]);
        list.add(first);

        for(int i=1;i<array.length;){
            TreeNode left=null,right=null;
            if(array[i]!=-1) {
                left = new TreeNode(array[i]);
            };
            if(array[i+1]!=-1) {
                right = new TreeNode(array[i+1]);
            };

            if (!list.isEmpty()) {
                TreeNode tmp = list.remove(0);
                if(tmp!=null) {
                    tmp.left = left;
                    tmp.right = right;
                }
                list.add(left);
                list.add(right);

            }

            i += 2;
        }
        return first;
    }