一、递归基础
递归就是函数调用自身。如果一个递归调用是最后一条执行语句，称为尾递归。递归模型由两部分组成：递归出口（结束条件）和递归体（递推关系）。
比如求 n!：
递归出口：fun(1) = 1
递归体：fun(n) = n * fun(n-1)
斐波那契数列也是递归的经典例子：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)。
在链表问题中，递归常常能写出非常简洁的代码，但也要注意理清调用过程。
二、反转链表（LeetCode 206）
题目：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
方法一：迭代法（双指针）
思路：定义两个指针，cur 指向当前节点，pre 指向前一个节点（初始为 null）。遍历链表，每次把 cur.next 指向 pre，然后 pre 和 cur 同时后移。循环结束返回 pre 即可。
代码：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while cur:
temp = cur.next # 保存下一个节点
cur.next = pre # 反转
pre = cur # pre 后移
cur = temp # cur 后移
return pre
方法二：递归法
思路：假设从节点 head.next 开始后面的链表已经反转完成，那么只需要把 head.next 的 next 指向 head，head.next 设为 null 即可。
代码：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return 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(next=head)
current = dummy_head
while current.next and current.next.next:
temp = current.next
temp1 = current.next.next.next
current.next = current.next.next
current.next.next = temp
temp.next = temp1
current = current.next.next
return dummy_head.next
