一、题目描述
给定一个单链表的头节点head
,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过1
。
示例 1
输入: head = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: 一个可能的答案是[0,-3, 9,-10, null, 5],它表示所示的高度平衡的二叉搜索树。
给定一个单链表的头节点head
,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过1
。
示例 1
输入: head = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: 一个可能的答案是[0,-3, 9,-10, null, 5],它表示所示的高度平衡的二叉搜索树。
给定一个二叉树:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
给定一个链表的头节点head
,返回链表开始入环的第一个节点。如果链表无环,则返回null
。
如果链表中有某个节点,可以通过连续跟踪next
指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从0
开始)。
如果pos
是-1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
给你一个链表的头节点head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪next
指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从0开始)。
注意:pos
不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回true
。否则返回false
。
给你两个单链表的头节点headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。
图示两个链表在节点 c1 开始相交:
题目数据保证整个链式结构中不存在环。
注意,函数返回结果后,链表必须保持其原始结构。
自定义评测:
评测系统
的输入如下(你设计的程序不适用
此输入):
给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。
示例 1
输入: head = [1, 2, 3, 4, 5], n = 2
输出: [1, 2, 3, 5]
示例 2
输入: head = [1], n = 1
输出: []
示例 3
输入: head = [1, 2], n = 1
输出: [1]
提示
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即:只能进行节点交换)。
示例 1
输入: head = [1, 2, 3, 4]
输出: [2, 1, 4, 3]
示例 2
输入: head = []
输出: []
示例 3
输入: head = [1]
输出: [1]
提示
给你单链表的头节点head,请你反转链表,并返回反转后的链表。
示例 1
输入: head = [1, 2, 3, 4, 5]
输出: [5, 4, 3, 2, 1]
示例 2
输入: head = [1, 2]
输出: [2, 1]
示例 3
输入: head = []
输出: []
提示
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性prev
以指示链表中的上一个节点。假设链表中的所有节点下标从0开始。
实现MyLinkedList类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将不会插入到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。