初级算法实践之链表、树、排序

零、背景

之前已经介绍了《初级算法实践之数组篇》和《初级算法实践之字符串篇》。

今天本打算介绍链表篇，但是发现大多数链表题都介绍了。
这里就给大家介绍链表、树、排序三种数据结构常见的题型，并找一道例题给大家讲解一下。

一、删除链表的倒数第N个节点

对于链表，常见的题其实不多。
比如反转、合并有序链表、排序、判断是否有环等等。
这里分享一个从链表删除节点的题。

题意：给一个链表，删除链表倒数第n个节点，并返回链表头。

思路：标准的做法是先得到链表的长度，然后计算出应该删除正序第几个，然后循环找到那个节点的父节点，进行删除。

而这里我介绍一种递归的写法。
递归的时候，对子链表节点个数进行统计，返回值为计算后的链表头节点。
计算逻辑则为判断当前子链表的头时候需要删除，需要则删除把下一个节点当做链表头。

二、对称二叉树

对于树，一般都是二叉树或者二叉搜索树上的问题。
比如树的最大深度、是否是二叉搜索树、遍历二叉树、数组转二叉搜索树等。
这里分享一道判断对称二叉树的题。

题意：给一个二叉树，判断是不是对称二叉树。

思路：递归判断即可。
关键递归的时候处理好左右子树的关系。

1.左子树和右子树要么都为空，要么都有节点。
2.左子树根节点和右子树根节点的值应该相等。
3.左子树的左儿子应该和右子树的右儿子相等。
4.左子树的右儿子应该和右子树的左儿子相等。

具体代码如下。

三、合并两个有序数组

对于数组的练习，实际上在数组篇已经介绍了。
这里再介绍一个双指针的练习题。

题意：给两个有序数组，求将第二个数值合并到第一个数组上，最终结果依旧有序。
要求：时间复杂度O(n)，空间复杂度O(1)。

思路：如果没有限制的话，直接把第二个追加到第一个数组，排序即可。
但是这个时间复杂度是O(n log(n))的。

如果我们使用合并排序的思想，则可以在线性时间内完成合并。
具体来说就是，不断的从两个数组里挑选最大的那个数字，挑之后对应的数组偏移量减一。
当其中一个数组为空时，那只能选择另外一个数组里的元素。

四、最后

这篇文章主要介绍一些基础的数据结构和算法。
比如链表题，删除节点往往最有挑战；
树的题型，往往使用递归解决； 数组的题型，则尽量使用双指针思路，扫描一遍来解决问题。

-EOF-