首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer第一天

剑指offer第一天

作者头像
郭耀华
发布2018-05-09 14:42:46
5850
发布2018-05-09 14:42:46
举报
文章被收录于专栏:郭耀华‘s Blog郭耀华‘s Blog

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;
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-01-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 15.反转链表
    • 输入一个链表,反转链表后,输出链表的所有元素。
      • 解法一:(使用栈)
      • 解法二:
  • 16.合并两个排序的链表
    • 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
      • 解法一:
      • 解法二:(使用递归)
  • 17.树的子结构
    • 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档