剑指Offer之Java算法习题精讲链表与二叉树专项训练

2024-04-02 19:04:59 724人浏览泡泡鱼

Python 官方文档：入门教程 => 点击学习

摘要

题目一链表题——反转链表根据单链表的头节点head来返回反转后的链表具体题目如下解法 class Solution { public Li

题目一

链表题——反转链表

根据单链表的头节点head来返回反转后的链表

具体题目如下

解法


class Solution {
    public Listnode reverseList(ListNode head) {
        ListNode pre,cur,nxt;
        pre = null;
        cur = head;
        nxt = head;
        while(cur!=null){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

题目二

链表题——反转链表

按照一定数量的节点来进行反转并返回反转之后的链表

具体题目如下

解法


class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
         if (head == null) return null;
         ListNode a, b;
         a = b = head;
         for (int i = 0; i < k; i++) {
            if (b == null) return head;
             b = b.next;
         }
         ListNode newHead = reverse(a, b);
         a.next = reverseKGroup(b, k);
         return newHead;
    }
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre,cur,nxt;
        pre = null;
        cur = a;
        nxt = a;
        while(cur!=b){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

题目三

链表题——回文链表

根据单链表的头节点head来判断该链表是否是回文链表，并返回结果

具体题目如下

解法：后序遍历与left比较


class Solution {
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);
    }
    boolean traverse(ListNode right){
        if (right == null) return true;
        boolean res = traverse(right.next);
        res = res && (right.val == left.val);
        left = left.next;
        return res;
    }
}

题目四

二叉树题——翻转二叉树

根据所给的二叉树根节点root来翻转此二叉树，并返回翻转后的二叉树根节点

具体题目如下

解法


class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode lf = invertTree(root.left);
        TreeNode rg = invertTree(root.right);
        root.left = rg;
        root.right = lf;
        return root;
    }
}

题目五

二叉树题——填充节点

给定一个完美二叉树，填充该二叉树每个节点的下一个右侧节点指针

具体题目如下

解法


 
class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        method(root.left,root.right);
        return root;
    }
    public void method(Node left,Node right){
        if (left == null || right == null) {
            return;
        }
        left.next = right;
        method(left.left,left.right);
        method(right.left,right.right);
        method(left.right,right.left);
    }
}

题目六

二叉树链表题——将二叉树展开为链表

根据给定的二叉树根节点root，将此二叉树展开为单链表

具体题目如下

解法


class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
 
        flatten(root.left);
        flatten(root.right);
 
        TreeNode left = root.left;
        TreeNode right = root.right;
 
        root.left = null;
        root.right = left;
 
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

到此这篇关于剑指Offer之Java算法习题精讲链表与二叉树专项训练的文章就介绍到这了,更多相关Java 链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 剑指Offer之Java算法习题精讲链表与二叉树专项训练

本文链接: https://www.lsjlt.com/news/143366.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341