1 链表的基础知识、递归方法的基本思路1.1 链表基础链表是一种非连续的线性存储结构。单链表由一个个节点构成每个节点包含数值val与后继指针next。依靠指针将全部节点串联。数组内存连续可以依靠下标快速访问元素链表内存分散无法随机读取遍历只能从头结点开始向后访问。但是链表插入、删除元素无需移动大量元素仅修改指针效率更高。Python单链表节点定义class ListNode:definit(self,val0,nextNone):self.val valself.next next1.2 链表递归解题思想递归分为两步向下递推、回溯处理。递归终止条件设置递归出口链表题目一般为head is None或者head.next is None代表遍历到链表末尾。递推调用函数处理后续子链表。回溯从链表尾部往头部完成节点操作、指针修改。核心思想不去纠结完整递归流程把func(head.next)当成已经处理完毕的、符合题目要求的链表接下来只需要处理当前节点和已经处理完成子链表之间的关系。2 LeetCode206 反转链表题目给定链表头节点反转整条链表返回反转后的新链表。递归实现class Solution:def reverseList(self, head):# 递归出口空链表 / 只剩尾结点直接返回if not head or not head.next:return headnew_head self.reverseList(head.next)# 回溯阶段反转指针head.next.next headhead.next Nonereturn new_head思路解析不断递归调用reverseList(head.next)一直抵达链表最后的节点。原链表尾节点作为反转之后的头结点new_head。回溯的时候令后一个节点指向当前节点。当前节点next置为空切断原有正向指针。将新头部逐层向上返回。迭代双指针实现class Solution:def reverseList(self, head):prev Nonecur headwhile cur:temp cur.nextcur.next prevprev curcur tempreturn prev设置prev前驱指针、cur当前指针。每次先暂存后继节点将当前节点反向指向prev两个指针同步向后移动循环结束prev就是反转完成的链表头。3 LeetCode24 两两交换链表中的节点题目两两交换相邻节点禁止修改节点内部val仅调整指针。递归写法class Solution:def swapPairs(self, head):# 剩余节点不足两个无需交换if not head or not head.next:return headsecond head.next# 后续链表完成两两交换head.next self.swapPairs(second.next)second.next headreturn second思路解析递归出口链表没有节点或者仅有一个节点。将后面剩余链表两两交换完成返回交换后的链表头部。交换当前的一对节点第二个节点变为本组新头部向上返回。迭代虚拟头结点class Solution:def swapPairs(self, head):dummy ListNode(0)dummy.next headcur dummywhile cur.next and cur.next.next:n1 cur.nextn2 cur.next.nextcur.next n2n1.next n2.nextn2.next n1cur n1return dummy.next新增虚拟节点dummy解决链表头部两个节点交换无前置节点的边界情况。cur作为每一对节点的前驱循环完成每组交换随后cur移动到交换后的后结点继续处理下一对。4 学习总结链表操作最关键的就是指针变更顺序很容易发生断链。递归解法思路简洁从后向前操作链表但是递归调用会开辟栈空间。迭代方式空间复杂度更低但是需要手动维护多个指针。