服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 剑指Offer之Java算法习题精讲链表与二叉树专项训练

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

2022-10-13 13:08明天一定. Java教程

跟着思路走，之后从简单题入手，反复去看，做过之后可能会忘记，之后再做一次，记不住就反复做，反复寻求思路和规律，慢慢积累就会发现质的变化

题目一

链表题——反转链表

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

具体题目如下

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

解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}

题目二

链表题——反转链表

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

具体题目如下

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

解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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来判断该链表是否是回文链表，并返回结果

具体题目如下

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

解法：后序遍历与left比较

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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来翻转此二叉树，并返回翻转后的二叉树根节点

具体题目如下

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

 解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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;
    }
}

题目五

二叉树题——填充节点

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

具体题目如下

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

解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
 
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，将此二叉树展开为单链表

具体题目如下

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

解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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 链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/wai_58934/article/details/123031314

  • Java
  • 链表
  • 二叉树

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    501 　 406 　 415 　 2000 　 1433 　 401 　 330 　 204 　 选择排序法 　 随机抽取 　 内存卡 　 下载器 　 十六进制字符 　 响应 　 静态工厂 　 构造函数 　 swt 　 Overview 　 对象池模式 　 InterProcessMutex 　 支票 　 金额大写转换 　 空心菱形 　 AspectJ 　 面向切面编程 　 方法名 　 网址信息 　 动态代理模式 　 线程安全 　 htmlparser 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图