著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你二叉树的根结点 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) 额外空间）展开这棵树吗？
前序遍历，原地递归修改
按照题意为前序遍历的结果，声明一个TreeNode pre记录前一个访问的节点
这样直接进行前序遍历，把当前节点挂载到pre节点的right上，记得要清除left节点
遍历当前节点的时候left、right节点的值记得先存下来，会在递归的时候被修改掉
class Solution {
/*
1
2 5
3 4 n 6
1
n 2
n 3
n 4
n 5
n 6
*/
TreeNode pre;
public void flatten(TreeNode root) {
dfs(root);
}
public void dfs(TreeNode node){
if (null == node){
return;
}
if (pre!=null){
pre.right = node;
}
pre = node;
TreeNode left = node.left;
TreeNode right = node.right;
node.left = null;
dfs(left);
dfs(right);
}
}给你一个链表，删除链表的倒数第 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]
提示：
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
双指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curN = head;
while (--n >= 0 && curN != null){
curN = curN.next;
}
if (curN==null){
return head.next;
}
ListNode cur = head;
curN = curN.next;
while (curN != null){
cur = cur.next;
curN = curN.next;
}
cur.next = cur.next.next;
return head;
}
}将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
[0, 50]-100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列双指针，串珠子
同剑指Offer25
这个问题之前给人家形象的比喻讲解过。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode cur = head;
while ( l1 != null || l2 != null ){
if (l1 == null || l2 == null){
cur.next = l1==null?l2:l1;
break;
}
if (l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
return head.next;
}
}
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/
遍历修改指针
修改指针
操作简单
next指向之前遍历的节点pre，这是核心next指向pre指向跟随遍历窗口移动到当前节点null节点，此时pre指向为原链表的结尾非空那个节点，也就是翻转后的头结点class Solution {
public ListNode reverseList(ListNode head) {
if (null == head || head.next == null){
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur!=null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/
双指针合并，不如找两串珠子自己比划比划
这个问题之前给人家形象的比喻讲解过。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode cur = head;
while ( l1 != null || l2 != null ){
if (l1 == null || l2 == null){
cur.next = l1==null?l2:l1;
break;
}
if (l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
return head.next;
}
}如果本题能够很好理解了不妨再去试试23. 合并K个升序链表
题解JAVA 分治归并 其实挺简单的
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4JAVA 分治归并 其实挺简单的
K/2个链表了，对剩下的链表继续两两合并//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]
- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 1){
return lists[0];
}
if (lists.length == 0){
return null;
}
int dis = 1;
while (dis < lists.length){
//1 [0,1],[2,3],[4,5],[6,7],[8]
//2 [0,2],[4,6],[8]
//4 [0,4],[8]
//8 [0,8]
for (int i = 0; i + dis < lists.length; i += dis*2) {
//合并两个有序链表 剑指Offer25题
lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
lists[i+dis] = null;
}
dis *=2;
}
return lists[0];
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
ListNode head = new ListNode();
ListNode cur = head;
while ( l1 != null || l2 != null ){
if (l1 == null || l2 == null){
cur.next = l1==null?l2:l1;
break;
}
if (l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
return head.next;
}
}给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
free 或 delete 被删除的节点遍历修改引用
val的节点，next指向当前值为val的节点的next节点val的节点的话，最红对链表结尾的判定val也没有匹配这个节点的值的话pre节点依旧为nullval的节点不止一个的话怎么处理呢？本题好像没这个情况class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head==null){
return head;
}
if (head.val == val){
return head.next;
}
ListNode cur = head;
ListNode pre = null;
while (val != cur.val && cur != null){
pre = cur;
cur = cur.next;
}
if (null!=pre){
pre.next = cur.next;
}
return head;
}
}