> 文档中心 > 算法学习打卡第二十二天 链表

算法学习打卡第二十二天 链表

 


目录

 一、题目

1、题目描述

2、基础框架

3、原题链接

二、解题报告

1、思路分析

2、代码详解

三、本题小知识


 一、题目

1、题目描述

给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换高度平衡二叉搜索树

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []输出: []

2、基础框架

   Java 版本给出的基础框架代码如下:   

/** * 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; } * } *//** * 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 sortedListToBST(ListNode head) {    }}

提示:

  • head 中的节点数在[0, 2 * 104] 范围内
  • -105 <= Node.val <= 105

 

3、原题链接

    LeetCode 109. 有序链表转换二叉搜索树

二、解题报告

1、思路分析

根据平衡二叉树的定义,我们知道选取链表的中间结点为根节点可满足平衡二叉树

  • 链表中间结点的查找
    1. 定义快慢指针,初始都指向链表的最左边
    2. 快指针每次移动两个结点,慢指针每次移动一个结点
    3. 当快指针指向尾结点或下一个结点为尾节点时(链表结点为奇数个或偶数个),慢指针指向中间节点
  • 构造平衡二叉树:
    1. 将链表中间结点做为平衡二叉树的根节点
    2. 递归构造左右子树

2、代码详解

/** * 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; } * } *//** * 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 sortedListToBST(ListNode head) {return  constructTree(head,null);    }    //定义构建平衡二叉树的方法    public TreeNode constructTree(ListNode left,ListNode right) { //链表为空则直接返回 if(left==right){     return null; } ListNode mid=getMid(left,right); //创建树根节点 TreeNode rood = new TreeNode(mid.val); //递归构造左子树 rood.left=constructTree(left,mid); //递归构造右子树 rood.right=constructTree(mid.next,right); return rood;    }    //定义获取中间结点的方法    public ListNode getMid(ListNode left,ListNode right){ //定义快慢指针 ListNode slow=left; ListNode quick=left; //让快指针移动两次,慢指针移动一次,当快指针指向尾节点或下一个就是尾结点时,慢指针指向中间节点 while(quick!=right&&quick.next!=right){     quick=quick.next;     quick=quick.next;     slow=slow.next; } return slow;    }}

三、本题小知识

   链表,快慢指针运用

    平衡二叉树(左右子树的高度相差不超过一)