前言

遍历二叉树是二叉树知识中的基础，有递归版本和非递归版本，这里递归的版本比较容易，所以我们只说前序遍历的递归形式，剩下的中序和后序由读者自行实现。本文着重写非递归形式的遍历。除了前中后序遍历外各位也可以自行实现层序遍历（一层一层遍历）。

前序、中序、后序遍历的定义

最简单的理解

1. 前序遍历：对于每个节点而言，先输出自身，再输出左子树，最后输出右子树的。(中左右)
2. 中序遍历：对于每个节点而言，先输出左子树，再输出自身，再输出右子树。（左中右）
3. 后序遍历：对于每个节点而言，先输出右子树，再输出左子树，再输出自身。（右左中）

问题

在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1
和head2，这两个链表可能相交，也可能不相交，请实现一个函数，如果两个
链表相交，请返回相交的第一个节点；如果不相交，返回null即可。要求:
如果链表1长度为N，链表2的长度为M,时间复杂度请达到O(N+M),额外空间
复杂度请达到O(1)。

本题可以分化成3个小问题

1. 判断单链表是否有环

2. 求两个无环单链表第一个相交的节点

3. 求两个有环单链表第一个相交的节点

环和相交的图例

我们可以先把每一个小问题都解决了再回头看整道题

问题

一种特殊的链表节点类描述如下：

1
2
3
4
5
6
7
8

public class Node {
    public int value;
    public Node next;
    public Node rand;
    public Node(int data){
        this.value = data;
    }
}

该类和正常节点拥有一样的功能，还新增了一个rand指针，可以指向链表钟的任意一个节点，也可以指向null。

请实现一个函数完成这个链表钟所有结构的复制，并返回复制的新链表的头节点。进阶：不用额外的数据结构，只用有限几个遍历，且再时间复杂度为O(N)内完成。

题目

将单向链表按某值划分为左边小、中间相等、右边大的形式

例子：

9->0->4->5->1,pivot=3,调整后为1->0->4->9->5

进阶：在原问题的基础上再增加两个要求，左中右三部分都要稳定性，要求时间复杂度为O(N),额外空间复杂度为O(1)。

例子：

9->0->4->5->1,pivot=3,调整后为
0->1->9->5->4

施工中。待补充有TODO字眼,记得c+f去补充
//如需要复习sql语句，请直接搜索表的定义

-本文的DDL文件和数据文件均可在https://www.db-book.com/db7/index.html下载。

第一章：概述数据库

数据库：

长期存储在计算机内，有组织的可共享的数据集合。

数据库管理系统：

数据库 + 一组用以访问、更新和管理这些数据的程序

DBMS的特性：

数据访问的高效和可扩展性
缩短应用开发时间
数据独立性(物理数据独立性/逻辑数据独立性)
数据完整性和安全性
并发访问和鲁棒性

题目

本题为leetcode206号题目

反转一个单链表

1
2

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题目

给定一个链表的头节点head,请判断该链表是否为回文结构。

例子: 1->2->1,返回true，1->2->2->1,返回true，1->2->3，返回false。

额外条件： 如果链表长为N，时间复杂度达到O(N),额外空间复杂度到达O(1)。

介绍

归并排序是一种采用分治思想实现的排序方式，大致的思路如下

把数组从中间分成前后两部分，然后对前后两部分都进行排序（不断分割，分割到一），再把两个排好序的数组合并，就完成啦。

接下来我们详细剖析一下各个步骤，深入理解归并排序。

题目

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

思路

这题目其实和快排的merge部分有点相似，忘了的兄弟萌可以去回忆一下。

因为两链表都是有序的，所以可以直接遍历对比。

两个链表比较两者当前的值，相等的话就输出并一起走一步，若是不同，较小者走一步，重复以上过程直到遍历完其中一个链表即可。