题目114、题目430、题目206、题目92、题目25
题目一描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
解题思路
后序遍历比较好，先处理子树，再对父节点有同样的操作。
代码实现
方法一：
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
// 后序遍历比较好
flatten(root.left);
flatten(root.right);
TreeNode temp = root.right;
// 左子树变为右子树
root.right = root.left;
root.left = null;
// 右子树接到左子树最右下角的右孩子
TreeNode right = root;
while (right.right != null) {
right = right.right;
}
right.right = temp;
}
}
题目二描述
430. 扁平化多级双向链表
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 3：
输入：head = []
输出：[]
说明：输入中可能存在空列表。
提示：
节点数目不超过 1000
1 <= Node.val <= 10^5
解题思路
类似的思路，可以看作一种二叉树，从子树开始展开，最后到全部。
代码实现
方法一：
class Solution {
public Node flatten(Node head) {
return dfs(head);
}
public Node dfs(Node head) {
if (head == null)
return null;
// 后序遍历
dfs(head.child);
dfs(head.next);
// 如果当前结点有child，进行操作
if (head.child != null) {
// 取出当前的next，后面要接到新的next最后
Node tempNext = head.next;
// 本结点的child连接到原来next的位置
head.child.prev = head;
head.next = head.child;
head.child = null;
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
// 原来的next连接到现在next的末尾
temp.next = tempNext;
tempNext.prev = temp;
}
return head;
}
}
题目三描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路
这是较为通用的一个模板，可以实现反转某个区间里的链表。
一定要背下来循环里的操作，每次先找next再反转，再移动。
代码实现
方法一：
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null)
return null;
ListNode dummyHead = new ListNode(0, head); // 虚拟头结点
ListNode ppre = dummyHead; // 找到要反转的结点的前一个，记录，最后要连接尾部结点
ListNode pre = dummyHead; // 找到要反转的结点的前一个，这个是要遍历用的
ListNode cur = head; // 这是要反转的结点
while (cur != null) {
ListNode nex = cur.next; // 1，要反转的结点的下一个
cur.next = pre; // 2，反转结点
pre = cur; // 3，pre移动到cur
cur = nex; // 4，cur移动到nex
}
ppre.next.next = cur; // 反转后的链表的尾结点连接到原来的后序结点上
ppre.next = pre; // ppre连接到反转之后链表的头结点
return dummyHead.next;
}
}
题目四描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
解题思路
先找到要反转的链表的前一个，再对这一段反转即可，也是模版题，注意反转次数。
代码实现
方法一：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null)
return head;
ListNode dummyHead = new ListNode(-1, head);
ListNode pre = dummyHead;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode ppre = pre;
ListNode cur = pre.next;
// 注意反转次数，这里是从第一个结点反转的，所以操作次数要加一
for (int i = 0; i < right - left + 1; i++) {
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
ppre.next.next = cur;
ppre.next = pre;
return dummyHead.next;
}
}
题目五描述
给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表 如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
可以转成数组然后双指针判断
也可以先找到链表中点，再反转链表后半部分，再两两对比判断。
代码实现
方法一：
class Solution {
public boolean isPalindrome(ListNode head) {
// 这里是排除只有一个结点的情况，以免以后有空指针的错误
if (head.next == null)
return true;
ListNode dummyHead = new ListNode(-1, head);
// 找到链表中点
ListNode slow = dummyHead;
ListNode fast = dummyHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 反转后部分
ListNode ppre = slow;
ListNode pre = ppre;
ListNode cur = pre.next;
while (cur != null) {
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
if (ppre.next != null) {
ppre.next.next = cur;
ppre.next = pre;
}
// 从两侧向内比对
ListNode left = dummyHead.next;
ListNode right = pre;
while (right != null) {
if (left.val != right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
}
}
题目六描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
解题思路
反转链表的重点是找到要反转的结点的前一个结点，所以如果这个结点有变动，就需要暂存并更新了。
代码实现
方法一：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyHead = new ListNode(-1, head);
// 计算总结点数，进而计算反转几组
int n = 0;
ListNode temp = dummyHead.next;
while (temp != null) {
temp = temp.next;
n++;
}
ListNode ppre = dummyHead;
ListNode pre = dummyHead;
ListNode cur = pre.next;
for (int group = 0; group < n / k; group++) {
for (int i = 0; i < k; i++) {
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
ListNode nextPPRE = ppre.next; // 每次要暂存下一组的上一个结点
ppre.next.next = cur;
ppre.next = pre;
ppre = nextPPRE;
}
return dummyHead.next;
}
}
