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

零、背景

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

今天本打算介绍链表篇，但是发现大多数链表题都介绍了。

这里就给大家介绍链表、树、 排序 三种数据结构常见的题型，并找一道例题给大家讲解一下。

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

对于链表，常见的题其实不多。

比如反转、合并有序链表、排序、判断是否有环等等。

这里分享一个从链表删除节点的题。

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

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

而这里我介绍一种递归的写法。

递归的时候，对子链表节点个数进行统计，返回值为计算后的链表头节点。

计算逻辑则为判断当前子链表的头时候需要删除，需要则删除把下一个节点当做链表头。

二、对称二叉树

对于树，一般都是二叉树或者二叉搜索树上的问题。

比如树的最大深度、是否是二叉搜索树、遍历二叉树、数组转二叉搜索树等。

这里分享一道判断对称二叉树的题。

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

思路：递归判断即可。

关键递归的时候处理好左右子树的关系。

1.左子树和右子树要么都为空，要么都有节点。

2.左子树根节点和右子树根节点的值应该相等。

3.左子树的左儿子应该和右子树的右儿子相等。

4.左子树的右儿子应该和右子树的左儿子相等。

具体代码如下。

三、合并两个有序数组

对于数组的练习，实际上在数组篇已经介绍了。

这里再介绍一个双指针的练习题。

题意：给两个有序数组，求将第二个数值合并到第一个数组上，最终结果依旧有序。

要求：时间复杂度 O(n) ，空间复杂度 O(1) 。

思路：如果没有限制的话，直接把第二个追加到第一个数组，排序即可。

但是这个时间复杂度是 O(n log(n)) 的。

如果我们使用合并排序的思想，则可以在线性时间内完成合并。

具体来说就是，不断的从两个数组里挑选最大的那个数字，挑之后对应的数组偏移量减一。

当其中一个数组为空时，那只能选择另外一个数组里的元素。

四、最后

这篇文章主要介绍一些基础的数据结构和算法。

比如链表题，删除节点往往最有挑战；

树的题型，往往使用递归解决； 数组的题型，则尽量使用双指针思路，扫描一遍来解决问题。

-EOF-