剑指Offer系列（3）

public class Solution {
    public void reOrderArray(int [] array) {
        int index = -1;
        int size = array.length;
        for(int i = 0;i<size;i++){
            //判断元素是否为奇数，不是就跳过
        	if(array[i] % 2 != 0){
                //判断两个奇数是否相邻，相邻index直接加1
        		if(i ==  index +1){
        			index = i;
        			continue;
        		}
                //不相邻进行偶数的移动和后一个奇数的向前插入
        		else{
        			int temp = array[i];
        			for(int j = i; j > index +1;j--){
        				array[j] = array[j-1];
        			}
        			array[index+1] = temp;
                    //index表示前半部分排列好的奇数中最后一个奇数的位置，所以插入后index要加1
        			index++;
        		}
        	}
        }
    }
}

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    	ListNode p = head;
    	ListNode q = head;
    	while(q != null){
    		q = q.next;
    		if(k < 1){
    			p = p.next;
    		}
    		k--;
    	}
    	//k值大于链表长度的情况
    	if(k >= 1){
    		return null;
    	}
    	return p;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
    	ListNode current = head;
    	ListNode temp = null;
    	ListNode pre = null;
    	ListNode newHead = null;
    	while(current != null){
    		temp = current.next;
    		current.next = pre;
    		pre = current;
    		current = temp;
    		if(temp == null){
    			newHead = pre;
    		}
    	}
    	return newHead;
    }
}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
    	ListNode newp = list1;
    	if(list1 == null){
    		return list2;
    	}
    	ListNode p1 = list1.next;
    	ListNode p2 = list2;
    	
    	while(p1 != null || p2 != null){
    		
    		if(p2 == null || p1 != null && p1.val <= p2.val){
    			newp.next = p1;
    			p1 = p1.next;
    			newp = newp.next;
    		}
    		else if(p1 == null || p2 != null && p1.val > p2.val){
    			newp.next = p2;
    			p2 = p2.next;
    			newp = newp.next;
    		}
    	}
        return list1;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	boolean result = false;
    	//如果二叉树B或者二叉树A为空树，直接返回false，无需比较
    	if(root2 == null || root1 == null){
    		return false;
    	}
    	//当两棵树都不为空时，首先在A中找到与B根节点值相同的结点
    	//从这个结点开始比较这个结点以下部分是否对B形成包含关系
    	if(root1.val == root2.val){
    		result = doesTree1HasTree2(root1, root2);
    	}
    	//如果这个结点不包含B，则递归，用A的左孩子代替A，进行比较
    	if(!result){
    		result = HasSubtree(root1.left, root2) ;
    	}
    	//如果左孩子以下不包含B，则再次递归，用A的右孩子代替A，进行比较
    	if(!result){
    		result = HasSubtree(root1.right, root2);
    	}
    	return result;
    }
    /**
     * 判断两个根节点相同的树，是否包含其中小的那一棵，即B中每个结点都能与A中一一对应
     * @param n1
     * @param n2
     * @return
     */
    public boolean doesTree1HasTree2(TreeNode n1, TreeNode n2){
    	//表示B遍历完了，所以是能够在A中一一对应的，返回true
    	if(n2 == null){
    		return true;
    	}
    	//B还没遍历完，A就已经遍历完了，说明A比B还要小，不可能包含B，返回false
    	if(n1 == null){
    		return false;
    	}
    	//如果有一个子结点的值不相同，直接返回false
    	if(n1.val != n2.val){
    		return false;
    	}
    	//严格保证每个结点的值都是相同的
    	return doesTree1HasTree2(n1.left, n2.left) && 
				doesTree1HasTree2(n1.right, n2.right);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

public class Solution {
    public void Mirror(TreeNode root) {
        //传入一个空树，直接返回
    	if(root == null){
    		return;
    	}
        //交换根节点的左右子树
    	TreeNode tmp = root.left;
		root.left = root.right;
		root.right = tmp;
        //有左孩子，进行左孩子递归
    	if(root.left != null){
    		Mirror(root.left);
    	}
        //有右孩子，进行右孩子递归
    	if(root.right != null){
    		Mirror(root.right);
    	}
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}