一、递归基础递归就是函数调用自身。如果一个递归调用是最后一条执行语句称为尾递归。递归模型由两部分组成递归出口结束条件和递归体递推关系。比如求 n!递归出口fun(1) 1递归体fun(n) n * fun(n-1)斐波那契数列也是递归的经典例子F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。在链表问题中递归常常能写出非常简洁的代码但也要注意理清调用过程。二、反转链表LeetCode 206题目给你单链表的头节点 head请你反转链表并返回反转后的链表。方法一迭代法双指针思路定义两个指针cur 指向当前节点pre 指向前一个节点初始为 null。遍历链表每次把 cur.next 指向 pre然后 pre 和 cur 同时后移。循环结束返回 pre 即可。代码class Solution:def reverseList(self, head: ListNode) - ListNode:cur headpre Nonewhile cur:temp cur.next # 保存下一个节点cur.next pre # 反转pre cur # pre 后移cur temp # cur 后移return pre方法二递归法思路假设从节点 head.next 开始后面的链表已经反转完成那么只需要把 head.next 的 next 指向 headhead.next 设为 null 即可。代码class Solution:def reverseList(self, head: ListNode) - ListNode:if not head or not head.next:return headnew_head self.reverseList(head.next)head.next.next headhead.next Nonereturn new_head三、两两交换链表中的节点LeetCode 24题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。不能修改节点内部的值只能进行节点交换。示例输入 [1,2,3,4]输出 [2,1,4,3]。思路使用虚拟头节点 dummy_head然后用指针 current 遍历。每次需要检查 current.next 和 current.next.next 是否存在。交换时需要三个临时指针temp 保存第一个节点temp1 保存第二个节点的下一个节点。然后调整指针current.next 指向第二个节点第二个节点指向第一个节点第一个节点指向 temp1。最后 current 移动到第一个节点即交换后的第二个节点继续循环。代码class Solution:def swapPairs(self, head: ListNode) - ListNode:dummy_head ListNode(nexthead)current dummy_headwhile current.next and current.next.next:temp current.nexttemp1 current.next.next.nextcurrent.next current.next.nextcurrent.next.next temptemp.next temp1current current.next.nextreturn dummy_head.next
