链表基本知识链表是一种线性的数据结构它的内存空间并不连续依靠节点之间的指针实现逻辑上的先后顺序本次主要学习单链表。链表的基础单元是节点每一个节点分为两个部分一部分用来存放实际的数据另一部分是指针用来指向链表的下一个节点。链表末尾的节点指针为空代表链表到此结束。头节点是链表的访问入口指向链表第一个节点如果头节点为空就代表这是一条空链表。单链表只能够顺着指针方向向后遍历无法直接随机访问链表中的任意位置。链表的优势是新增、删除节点时只需要改动指针指向不需要移动大量数据缺点是查找数据必须从头开始逐个向后遍历。链表常见的算法题目有链表反转、两两交换相邻节点。做题时经常会用到虚拟头节点创建一个额外的虚拟节点让它指向原来链表的头节点。使用虚拟头节点可以统一处理各类边界情况最后返回虚拟头节点的下一个节点就是处理完成后的链表。递归方法的基本思路递归指的是一个函数或者过程在执行的过程中调用自身。如果函数直接自己调用自己叫做直接递归如果一个函数调用另一个函数被调用的函数又回过头调用原函数叫做间接递归。当递归调用是函数中最后执行的语句时这种递归称为尾递归。一个完整的递归模型由递归出口和递归体两部分构成。递归出口就是递归的终止条件当问题缩小到足够简单时直接给出结果不再继续递归调用避免无限循环。递归体描述问题的递推关系把规模较大的原问题拆解成规模更小、逻辑相同的子问题建立原问题结果和子问题结果之间的联系。通常有三类场景适合使用递归第一类是事物本身的定义就是递归的例如阶乘、斐波那契数列第二类是数据结构具备递归特性比如链表去掉头部节点之后剩下的部分依旧是链表第三类是问题的求解思路适合递归可以把大问题拆解成同类型的子问题求解。使用递归解题首先要确定递归出口找到最小规模的问题直接返回结果其次编写递归体将原问题拆解为子问题调用递归求解子问题最后利用子问题得到的结果完成当前层级的处理向上返回结果。递归运行时会依托函数调用栈先一层层向下递推直到触发递归出口之后再一层一层回溯把结果回传。递归的弊端是如果递归深度过大容易发生栈溢出。链表相关算法既可以用循环迭代实现也可以使用递归实现迭代依靠循环重复执行逻辑递归依靠函数自身调用完成逻辑。