15.反转链表

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

解法一：（使用栈）

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/import java.util.Stack;public class Solution {    public ListNode ReverseList(ListNode head) {        Stack
    
      stack = new Stack<>();        if(head == null) return null;        while(head != null){            stack.push(head);            head = head.next;        }                head = stack.pop();        ListNode temp = head;        while(!stack.empty()){            temp.next = stack.pop();            temp = temp.next;        }        temp.next = null;//一定要注意这里的这行代码        //一定要将链表末位next置为null        return head;    }}
    

解法二：

public class Solution{    public ListNode ReverseList(ListNode head){        ListNode reversedListHead;        ListNode pre = null;        ListNode node = null;        ListNode next = null;        if(head == null) return null;        node = head;        while(true){            next = node.next;            node.next = pre;            pre = node;            if(next == null){                reversedListHead = node;                break;            }               node = next;        }        return reversedListHead;    }}

16.合并两个排序的链表

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

解法一：

public class Solution {    public ListNode Merge(ListNode list1,ListNode list2) {        //if(list1 == null && list2 == null) return null;        //这行代码可以不要，因为当list1 == null  return list2也等于null        if(list1 == null) return list2;        if(list2 == null) return list1;        ListNode head,node;        if(list1.val <= list2.val){            node = list1;            head = node;            list1 = list1.next;        }else{            node = list2;            head = node;            list2 = list2.next;        }        while(list1 != null&&list2 != null){            if(list1.val<=list2.val){                node.next = list1;                list1 = list1.next;                node = node.next;            }else{                node.next = list2;                list2 = list2.next;                node = node.next;            }        }        while(list1 != null){            node.next = list1;            list1 = list1.next;            node = node.next;        }        while(list2 != null){            node.next = list2;            list2 = list2.next;            node = node.next;        }        return head;    }}

解法二：（使用递归）

public class Solution {    public ListNode Merge(ListNode list1,ListNode list2) {        if(list1 == null) return list2;        if(list2 == null) return list1;        ListNode MergedHead = null;        if(list1.val <= list2.val){            MergedHead = list1;            MergedHead.next = Merge(list1.next,list2);        }else{            MergedHead = list2;            MergedHead.next = Merge(list1,list2.next);        }        return MergedHead;    }}

17.树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**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(root1==null||root2==null) return false;        boolean result = false;        if(root1.val == root2.val){            result = isEqualTree(root1,root2);        }        if(!result)            result = HasSubtree(root1.left,root2);        if(!result)            result = HasSubtree(root1.right,root2);        return result;    }    public boolean isEqualTree(TreeNode tree1,TreeNode tree2){        //注意此处，只需判断tree2 == null即可返回true；        //因为tree2为子树，此时tree1可以不为null，即tree1不为叶节点        if(tree2 == null) return true;         if(tree1 == null) return false;        if(tree1.val == tree2.val){            return isEqualTree(tree1.left,tree2.left) && isEqualTree(tree1.right,tree2.right);        }        return false;    }}