如何用递归法找出两个有序链表的公共节点与独有节点？

递归实现的核心是把问题拆解成「处理当前两个链表的头节点」+「递归处理剩余的链表部分」，逻辑和你已经掌握的迭代法完全对应，只是把循环遍历换成了函数自调用。下面直接给你思路和代码示例：

核心思路 #

我们需要一个递归函数，它接收当前遍历到的l1和l2节点，返回一个包含两个链表头的结果：一个是当前处理后生成的common链表头，另一个是unique链表头。每次处理只关注当前的两个节点，剩下的交给递归处理。

具体逻辑（分情况处理） #

1. 终止条件：

   • 如果l1和l2都为空：直接返回(null, null)，没有节点需要处理
   • 如果l1为空：剩下的l2所有节点都是独有节点，新建节点存l2->data，然后递归处理l1和l2->next，把当前节点和递归返回的unique链表连起来，返回(null, 当前unique节点)
   • 如果l2为空：和上面逻辑对称，新建节点存l1->data，递归处理l1->next和l2，返回(null, 当前unique节点)

2. 当前节点处理：

   • 当l1->data < l2->data：
     新建unique节点存l1->data，递归处理l1->next和l2，得到后续的common和unique链表，把当前unique节点的next指向递归返回的unique链表头，最终返回(递归得到的common头, 当前unique节点)
   • 当l1->data > l2->data：
     和上面逻辑对称，新建unique节点存l2->data，递归处理l1和l2->next，返回(递归得到的common头, 当前unique节点)
   • 当l1->data == l2->data：
     新建common节点存该值，递归处理l1->next和l2->next，把当前common节点的next指向递归返回的common链表头，最终返回(当前common节点, 递归得到的unique头)

代码示例（C语言） #

#include <stdlib.h>

// 链表节点结构
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

// 定义返回结果的结构体，存储common和unique的头节点
typedef struct Result {
    ListNode *common;
    ListNode *unique;
} Result;

// 新建节点辅助函数
ListNode* createNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = val;
    node->next = NULL;
    return node;
}

// 递归处理函数
Result splitLists(ListNode* l1, ListNode* l2) {
    Result res = {NULL, NULL};
    
    // 终止条件1：两个链表都为空
    if (!l1 && !l2) {
        return res;
    }
    // 终止条件2：l1为空，处理剩余l2
    if (!l1) {
        res.unique = createNode(l2->data);
        Result rest = splitLists(l1, l2->next);
        res.unique->next = rest.unique;
        res.common = rest.common;
        return res;
    }
    // 终止条件3：l2为空，处理剩余l1
    if (!l2) {
        res.unique = createNode(l1->data);
        Result rest = splitLists(l1->next, l2);
        res.unique->next = rest.unique;
        res.common = rest.common;
        return res;
    }
    
    // 处理当前节点
    if (l1->data < l2->data) {
        res.unique = createNode(l1->data);
        Result rest = splitLists(l1->next, l2);
        res.unique->next = rest.unique;
        res.common = rest.common;
    } else if (l1->data > l2->data) {
        res.unique = createNode(l2->data);
        Result rest = splitLists(l1, l2->next);
        res.unique->next = rest.unique;
        res.common = rest.common;
    } else {
        // 数据相等，加入common
        res.common = createNode(l1->data);
        Result rest = splitLists(l1->next, l2->next);
        res.common->next = rest.common;
        res.unique = rest.unique;
    }
    
    return res;
}

调用示例 #

比如你给出的例子：l1 = 1->3->5->8，l2 = 3->4->8->9，调用splitLists(l1, l2)后，会得到：

• common链表：3->8
• unique链表：1->5->4->9

这个递归逻辑完全对应迭代法的处理顺序，只是用函数自调用代替了循环的指针移动，每一步只处理当前的节点，剩余的交给递归完成。

内容的提问来源于stack exchange，提问作者taurus05