剑指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;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jack-Cui

234. Palindrome Linked List(Linked List-Easy)

Given a singly linked list, determine if it is a palindrome. Follow up: Could yo...

19710
来自专栏赵俊的Java专栏

链表求和 Ⅱ

1284
来自专栏小二的折腾日记

LeetCode-23-Merge-k-Sorted-Lists

这个题乍一看只是对链表的一个排序,因为是很多个链表,所以很简单的想法就是将整个数组里面的两个链表分别进行排序。两个两个互相排序之后就能排好。这里用的是递归。当v...

842
来自专栏desperate633

替换空格

862
来自专栏LeetCode

LeetCode 206. Reverse Linked List

1042
来自专栏desperate633

LintCode 翻转链表题目分析代码

样例 给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

863
来自专栏Jack-Cui

160. Intersection of Two Linked Lists(Linked List-Easy)

    Write a program to find the node at which the intersection of two singly lin...

2345
来自专栏desperate633

LeetCode 160. Intersection of Two Linked Lists题目分析

请写一个程序,找到两个单链表最开始的交叉节点。 ** 注意事项 ** 如果两个链表没有交叉,返回null。 在返回结果后,两个链表仍须保持原有的结构。 ...

962
来自专栏mathor

LeetCode86. 分隔链表

 这道题类似荷兰国旗,说一下做法,最简单的方法就是直接将所有的值保存到数组中,然后对数组进行划分,完了以后再重新插回链表中。但是这道题有一个附加要求,要保留...

895
来自专栏计算机视觉与深度学习基础

Leetcode 61 Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative...

20710

扫码关注云+社区

领取腾讯云代金券