剑指offer第一天

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<ListNode> 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;

    }

}

巴特西

剑指offer第一天

15.反转链表

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

解法一：（使用栈）

解法二：

16.合并两个排序的链表

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

解法一：

解法二：（使用递归）

17.树的子结构

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

最新文章

热门文章