链表系列之递归

递归的本质

递归是一种将大问题分解为相同结构小问题的编程技巧

在链表中，递归特别适用，因为链表本身就是递归定义的：

• 链表 = 头节点 + 剩余链表
• 剩余链表 = 头节点 + 剩余链表
• …直到空节点

递归解决链表问题的核心三要素：

1. 递归终止条件：什么时候停止递归
2. 递归逻辑：如何处理当前节点
3. 返回值：向上一层返回什么

---

入门篇：反转链表

LeetCode 206. 反转链表

问题描述

给定一个链表，反转整个链表并返回新的头节点

递归思路

假设链表为：1 → 2 → 3 → 4 → 5

递归的思考方式：

1. 先递归反转 2 → 3 → 4 → 5，得到 5 → 4 → 3 → 2
2. 然后处理节点1，让2的next指向1
3. 将1的next设为NULL

代码实现

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

递归过程图解

原链表：1 → 2 → 3 → NULL

递归栈：
第1层：reverseList(1) 
第2层：  reverseList(2)
第3层：    reverseList(3)
第4层：      reverseList(NULL) → 返回3

回溯过程：
第3层：3已反转，处理2 → 3 → 2，2.next = NULL
       返回3
第2层：3 → 2已反转，处理1 → 2 → 1，1.next = NULL
       返回3

最终：3 → 2 → 1 → NULL

关键点

• 终止条件：head为空或head->next为空
• 核心操作：head->next->next = head（让下一个节点指向当前节点）
• 断开原连接：head->next = NULL（避免成环）
• 返回值：新的头节点（始终是原链表的尾节点）

---

进阶篇一：合并两个有序链表

LeetCode 21. 合并两个有序链表

问题描述

将两个升序链表合并为一个新的升序链表

递归思路

每次选择两个链表中较小的头节点，然后递归处理剩余部分

代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

递归过程示例

list1: 1 → 3 → 5
list2: 2 → 4 → 6

第1层：比较1和2，选1，递归merge(3→5, 2→4→6)
第2层：比较3和2，选2，递归merge(3→5, 4→6)
第3层：比较3和4，选3，递归merge(5, 4→6)
第4层：比较5和4，选4，递归merge(5, 6)
第5层：比较5和6，选5，递归merge(NULL, 6)
第6层：返回6

回溯构建：1 → 2 → 3 → 4 → 5 → 6

关键点

• 终止条件：任一链表为空，返回另一个链表
• 递归逻辑：选择较小的节点，将其next指向递归结果
• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)（递归栈深度）

---

进阶篇二：两两交换链表节点

LeetCode 24. 两两交换链表中的节点

问题描述

给定一个链表，两两交换其中相邻的节点

例如：1 → 2 → 3 → 4 变为 2 → 1 → 4 → 3

递归思路

1. 递归处理后续节点（从第3个节点开始）
2. 交换当前的两个节点
3. 返回新的头节点

代码实现

struct ListNode* swapPairs(struct ListNode* head) {
    if(!head || !head->next)
        return head;
    
    struct ListNode* cur = head;
    struct ListNode* next = head->next;
    struct ListNode* tmp = next->next;
    
    next->next = cur;
    cur->next = swapPairs(tmp);
    
    return next;  // 新的头节点
}

递归过程图解

原链表：1 → 2 → 3 → 4

第1层：处理1和2
       递归处理3 → 4
第2层：处理3和4
       递归处理NULL
       返回4
       
回溯：
第2层：交换3和4，返回 4 → 3
第1层：交换1和2，连接返回结果
       2 → 1 → (4 → 3)
       返回2

最终：2 → 1 → 4 → 3

关键点

• 终止条件：节点为空或只剩一个节点
• 保存三个关键指针：cur、next、tmp
• 返回值：交换后的新头节点（原来的第二个节点）

---

高级篇一：K个一组翻转链表

LeetCode 25. K 个一组翻转链表

问题描述

给定一个链表，每k个节点一组进行翻转

例如：1 → 2 → 3 → 4 → 5，k=2
结果：2 → 1 → 4 → 3 → 5

递归思路

1. 检查是否有k个节点
2. 如果有，翻转前k个节点
3. 递归处理剩余部分
4. 连接翻转后的部分和递归结果

代码实现

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    // 检查是否有k个节点
    struct ListNode *p = head;
    for(int i = 0; i < k; i++) {
        if(!p) return head;  // 不足k个，直接返回head
        p = p->next;
    }
    
    // 翻转前k个节点
    struct ListNode *q = head;
    struct ListNode *pre = NULL;
    
    while(q != p) {  // 翻转从head到p的前k个节点
        struct ListNode *tmp = q->next;
        q->next = pre;
        pre = q;
        q = tmp;
    }

    head->next = reverseKGroup(p, k);
    return pre;
}

递归过程示例

原链表：1 → 2 → 3 → 4 → 5，k=2

第1层：检查1,2存在
       翻转1,2 得到 2 → 1
       递归处理3 → 4 → 5
       
第2层：检查3,4存在
       翻转3,4 得到 4 → 3
       递归处理5
       
第3层：检查5后不足2个
       直接返回5

回溯连接：
第2层：4 → 3 → 5，返回4
第1层：2 → 1 → (4 → 3 → 5)，返回2

最终：2 → 1 → 4 → 3 → 5

关键点

• 先检查是否有足够的节点
• 翻转逻辑与普通反转链表相同
• 递归处理剩余部分
• head变成了翻转后这组的尾节点

---

高级篇二：排序链表（归并排序）

LeetCode 148. 排序链表

问题描述

对链表进行排序，要求时间复杂度O(n log n)

递归思路（分治法）

归并排序的经典应用：

1. 找到链表中点（快慢指针）
2. 递归排序左半部分
3. 递归排序右半部分
4. 合并两个有序链表

代码实现

// 找到链表中间节点
struct ListNode* findMiddle(struct ListNode* head) {
    if (!head || !head->next) return head;
    
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 递归归并排序主函数
struct ListNode* sortList(struct ListNode* head) {
    // 递归终止条件：空链表或单节点
    if (!head || !head->next) {
        return head;
    }
    
    // 1. 找到中间节点并分割
    struct ListNode* mid = findMiddle(head);
    struct ListNode* right = mid->next;
    mid->next = NULL;  // 切断链表
    
    // 2. 递归排序左右两部分
    struct ListNode* leftSorted = sortList(head);
    struct ListNode* rightSorted = sortList(right);
    
    // 3. 合并有序链表
    return merge(leftSorted, rightSorted);
}

递归过程图解

原链表：4 → 2 → 1 → 3

分割阶段：
层1：[4,2,1,3] → [4,2] 和 [1,3]
层2：[4,2] → [4] 和 [2]
     [1,3] → [1] 和 [3]

合并阶段：
层2：merge([4], [2]) → [2,4]
     merge([1], [3]) → [1,3]
层1：merge([2,4], [1,3]) → [1,2,3,4]

最终：1 → 2 → 3 → 4

关键点

• 分治思想：分割、递归、合并
• 快慢指针找中点
• 切断链表很重要（mid->next = NULL）
• 时间复杂度：O(n log n)
• 空间复杂度：O(log n)（递归栈）

---

高级篇三：复制带随机指针的链表

LeetCode 138. 随机链表的复制

问题描述

复制一个特殊的链表，每个节点除了next指针，还有一个random指针指向链表中的任意节点或null

递归思路

使用哈希表缓存已复制的节点，递归复制next和random

代码实现

struct HashTable {
    struct Node *key, *val;
    UT_hash_handle hh;
} * cachedNode;

struct Node* deepCopy(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    
    struct HashTable* tmp;
    HASH_FIND_PTR(cachedNode, &head, tmp);
    
    if (tmp == NULL) {
        // 创建新节点
        struct Node* headNew = malloc(sizeof(struct Node));
        headNew->val = head->val;
        
        // 加入哈希表
        tmp = malloc(sizeof(struct HashTable));
        tmp->key = head;
        tmp->val = headNew;
        HASH_ADD_PTR(cachedNode, key, tmp);
        
        // 递归复制next和random
        headNew->next = deepCopy(head->next);
        headNew->random = deepCopy(head->random);
    }
    
    return tmp->val;
}

struct Node* copyRandomList(struct Node* head) {
    cachedNode = NULL;
    return deepCopy(head);
}

关键点

• 使用哈希表避免重复复制同一个节点
• 先复制当前节点，再递归复制next和random
• 哈希表的key是原节点，value是新节点
• 递归可能会形成环，哈希表防止无限递归

---

递归核心总结

递归三要素

ReturnType recursive(Node* head) {
    // 1. 递归终止条件
    if (终止条件) {
        return 终止值;
    }
    
    // 2. 递归调用
    ReturnType result = recursive(下一个节点);
    
    // 3. 处理当前节点
    处理当前节点与递归结果;
    
    // 4. 返回结果
    return 返回值;
}

常见递归模式

模式一：自底向上
先递归到底，回溯时处理
例如：反转链表

模式二：自顶向下
先处理当前节点，再递归
例如：复制链表

模式三：分治合并
分割问题，递归处理，合并结果
例如：归并排序

---

总结

递归是解决链表问题的强大工具

掌握递归的关键：

• 明确递归三要素：终止条件、递归逻辑、返回值
• 理解递归的本质：将大问题分解为小问题
• 学会画递归树，理解回溯过程
• 权衡递归与迭代的优劣