合并两个有序链表递归解法为什么每次递归都返回当前链表头？

你猜测返回l1/l2是为了最终返回合并后链表头节点的结论是正确的，但这个返回值的作用不止服务于最外层调用，每一层递归返回的都是当前两个输入链表合并完成后的子链表头节点，用来给上一层递归做指针拼接。

我们可以用个具体示例拆解执行流程，你就能清晰看到返回值的作用：
假设待合并的两个链表为：

• l1：1 → 3 → None
• l2：2 → 4 → None

递归执行步骤拆解

1. 第一层调用（入参l1=节点1，l2=节点2）
   比较1和2，节点1值更小，所以需要把节点1的next指针，指向「剩余链表3→None和2→4→None的合并结果」，触发递归调用mergeTwoLists(l1.next, l2)
2. 第二层调用（入参l1=节点3，l2=节点2）
   比较3和2，节点2值更小，所以需要把节点2的next指针，指向「剩余链表3→None和4→None的合并结果」，触发递归调用mergeTwoLists(l1, l2.next)
3. 第三层调用（入参l1=节点3，l2=节点4）
   比较3和4，节点3值更小，所以需要把节点3的next指针，指向「剩余链表None和4→None的合并结果」，触发递归调用mergeTwoLists(l1.next, l2)
4. 第四层调用（入参l1=None，l2=节点4）
   触发边界条件l1 is None，直接返回l2（也就是节点4，对应子链表4→None）
5. 回溯到第三层
   节点3的next拼接刚才返回的节点4，当前层合并后的子链表为3→4→None，返回当前子链表的头节点l1（节点3）
6. 回溯到第二层
   节点2的next拼接刚才返回的节点3，当前层合并后的子链表为2→3→4→None，返回当前子链表的头节点l2（节点2）
7. 回溯到第一层
   节点1的next拼接刚才返回的节点2，最终合并后的完整链表为1→2→3→4→None，返回当前子链表的头节点l1（节点1），就是最终结果。

核心逻辑总结

每一层递归只做3件事：

• 选当前两个链表头中更小的节点作为当前子链表的头
• 把这个头的next指针，指向剩下的两个链表合并后的子链表头（就是下一层递归的返回值）
• 返回当前选出来的这个头，给上一层做拼接

这样一层层递归+回溯，就把所有节点按从小到大的顺序串成了完整的有序链表。

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