递归与链表学习笔记一、链表的基本知识1.什么是链表链表是一种常见的线性数据结构它由一系列节点Node组成。与数组不同链表中的元素在内存中不是连续存储的而是通过每个节点中的指针或引用将各个节点串联在一起。2 .链表的基本结构一个典型的链表节点包含两个部分数据域存储该节点所携带的数据。指针域存储指向下一个节点的指针在双向链表中还会有一个指向前一个节点的指针。链表的入口通常称为头结点head通过头结点可以遍历整个链表链表的最后一个节点的指针指向null或空指针表示链表的结束。3.链表的优缺点优点动态扩容不需要像数组那样预先分配固定大小的内存插入和删除节点时只需调整指针无需移动大量元素。内存利用率高按需分配节点空间。缺点不支持随机访问要访问某个特定位置的节点必须从头结点开始逐个遍历时间复杂度为O(n)。需要额外的指针存储空间。4.链表的常见操作常见的链表操作包括遍历链表在头部/尾部/指定位置插入节点删除指定节点反转链表合并多个链表检测链表是否有环等二、递归方法的基本思路1.什么是递归递归是指在定义一个过程或函数时出现调用本过程或本函数自身的成分。简单来说就是“自己调用自己”。若函数直接调用自身称为直接递归。若函数A调用函数B而函数B又调用了函数A称为间接递归。2.递归的两大核心要素一个正确的递归算法通常由两部分组成递归出口终止条件明确递归何时结束给出最简子问题的直接解。没有递归出口递归将无限进行下去导致栈溢出。递归体递推关系确定如何将原问题分解为规模更小的子问题并建立原问题与子问题之间的关系。例如求n!的递归模型递归出口当n1时返回1。递归体当n1时fun(n) n * fun(n-1)即当前问题的解依赖于规模更小的子问题的解。3.尾递归如果一个递归函数中递归调用语句是最后一条执行语句则称这种递归为尾递归。尾递归通常更容易被编译器优化以减少栈空间的占用。4.递归的适用场景以下三种情况常常适合使用递归方法1.定义本身就是递归的例如斐波那契数列F(n) F(n-1) F(n-2)2.数据结构本身是递归的例如链表、树、图等结构可以递归地定义和操作。3.问题的求解方法是递归的例如汉诺塔问题、分治算法、回溯算法等。5 .经典案例斐波那契数列斐波那契数列从第3项开始每一项都等于前两项之和。其数学定义为F(0) 0F(1) 1F(n) F(n-1) F(n-2)n ≥ 2斐波那契数列天然适合用递归实现因为它的定义本身就是递归的。但需要注意的是直接递归求解会存在大量重复计算实际应用中常结合记忆化搜索或动态规划进行优化。三、链表与递归的结合链表本身具有天然的递归性质——一个链表可以看作由头结点和剩余子链表组成。因此许多链表操作都可以用递归的方式简洁地实现例如反转链表将当前节点的下一个节点之后的子链表先反转再调整当前节点和下一个节点的指针关系。两两交换链表中的节点将前两个节点交换然后递归处理剩余的子链表。递归法处理链表问题时通常需要明确递归出口当链表为空或只剩一个节点时无需操作递归体如何处理当前节点与子链表之间的关系四、课后作业leetcode 206做题步骤1.初始化指针 pre None cur 指向链表头结点 head​2. 当 cur 不为空就进入循环​1.temp cur.next 先保存cur原本的下一个节点防止链表断掉后续找不到后面的结点​2. cur.next pre 把当前节点的next指向前面结点完成反转​3. pre cur pre向后移动更新为当前结点​4. cur temp cur向后移动到之前保存的旧下一个结点​3. while循环结束 cur 变成 None pre 就是反转之后链表的新头结点​4. 返回 pre题到代码逐行解析pre None 反转之后原来第一个节点会变成最后一个节点最后一个节点的next必须是 None 所以pre初始赋值None​cur head cur遍历链表从链表头部开始​while cur: 只要当前结点不为空代表还有结点需要反转​temp cur.next 核心保存cur后面的链表。如果直接写 cur.nextpre 后面链表直接丢失无法继续遍历。temp临时存下后面的结点。​cur.next pre 改变指针方向当前节点掉头指向前面节点完成单个节点反转。​pre cur pre往前走一步pre更新为当前节点作为下一轮的“前节点”​cur temp cur往前走一步去到之前保存好的原始下一个结点继续循环处理剩下节点​return pre 循环结束cur是Nonepre停在原链表最后一个结点也就是反转链表的头结点直接返回。leetcode 24做题步骤1.创建虚拟头结点dummy dummy.next 指向head解决头部节点交换的特殊情况 cur 从dummy出发。​2. 循环条件 cur.next 和 cur.next.next 都不为空说明后面还有2个节点可以交换。​3. 暂存两个临时节点​temp1 第一节点​temp2 下一组的第一个节点保存后续链表防止断裂​4. 执行交换​1.cur.next cur.next.next cur指向第二个节点第二个节点换到前面​2. cur.next.next temp1 第二个节点的next指向原来第一个节点​3. temp1.next temp2 原来第一个节点接上后面未处理链表​5. cur cur.next.next cur跳两组去到下一组的前一个位置继续循环。​6. 循环结束返回 dummy.next 作为新链表头。逐行代码解析dummy ListNode() 虚拟头结点链表题常用技巧统一头结点和普通节点操作逻辑不用单独处理头节点交换。​dummy.next head 虚拟头接在原链表最前面。​cur dummy cur作为遍历指针从虚拟头开始。​while cur.next and cur.next.next: 必须同时存在两个节点才可以两两交换只剩1个或者没有节点直接退出循环。​temp1 cur.next 保存本组第一个节点。​temp2 cur.next.next.next 保存下一组的开头交换会覆盖next必须提前存防止链表丢失。​cur.next cur.next.next cur直接连上本组第二个节点把第二个节点提前。​cur.next.next temp1 第二个节点的next指向原来第一个节点完成两个节点互换。​temp1.next temp2 原来第一个节点接上后面还没处理的链表。​cur cur.next.next cur向后移动两位跳到下一组的前置位置。​return dummy.next 虚拟头的next就是交换完成后的真正头结点。