如何用递归无辅助方法合并两个降序单链表为升序链表？

首先，得先纠正一个小细节：你当前贴的代码其实是用来合并升序链表得到升序结果的，而非降序。如果要合并两个降序链表输出降序，正确的递归逻辑应该是优先取更大的节点作为当前头，再递归拼接剩余部分，像这样：

public Node mergeByRecursion(Node node1, Node node2) { 
    if (node1 == null) { return node2; } 
    else if (node2 == null) { return node1; } 
    // 取更大的节点当头，保证降序
    if (node1.value > node2.value) { 
        node1.next = mergeByRecursion(node1.next, node2); 
        return node1; 
    } else { 
        node2.next = mergeByRecursion(node1, node2.next); 
        return node2; 
    } 
}

好了，回到你的问题：要在不创建辅助方法的前提下，把输出改成升序。这里有两种可行思路，我给你拆解清楚：

思路1：从后往前递归构建升序链表 #

因为输入是降序链表，最小的节点藏在链表末尾，我们可以递归钻到两个链表的最后，再从尾到头拼接节点，直接生成升序链表。不过这里要调整递归的返回逻辑——我们让递归返回当前构建好的升序链表的尾节点，最后再回溯找到头节点：

public Node mergeAscending(Node node1, Node node2) {
    if (node1 == null) return node2;
    if (node2 == null) return node1;

    Node tail;
    if (node1.value > node2.value) {
        // node1更大，应该放在升序链表的最后，先递归处理node1的后续节点和node2
        tail = mergeAscending(node1.next, node2);
        tail.next = node1;
        node1.next = null; // 防止出现循环引用
        return node1; // 返回新的尾节点
    } else {
        // node2更大，同理处理
        tail = mergeAscending(node1, node2.next);
        tail.next = node2;
        node2.next = null;
        return node2;
    }
}

⚠️ 注意：这个方法返回的是升序链表的尾节点，如果你需要头节点，得从尾节点往前遍历到最前端（或者你可以在递归过程中用类成员变量记录头节点，但那样也算一种“辅助”）。这种方式不需要额外反转，但代码逻辑稍绕，不过总时间复杂度还是O(n)。

思路2：先合并降序，再递归反转（最优方案） #

这其实是最实用也最高效的方案——复用你已经写好的降序合并逻辑，先得到降序链表，再通过递归反转得到升序结果。虽然看起来是两步，但时间复杂度还是O(n)（合并O(n) + 反转O(n)），空间复杂度也是O(n)（递归栈开销），属于链表操作的常规技巧。

如果允许创建一个极小的反转方法（毕竟逻辑独立且简洁），代码会非常清晰：

public Node mergeAscending(Node node1, Node node2) {
    // 先合并成降序
    Node descending = mergeByRecursion(node1, node2);
    // 反转得到升序
    return reverse(descending);
}

// 反转链表的递归方法，逻辑很简洁
private Node reverse(Node head) {
    if (head == null || head.next == null) return head;
    Node reversedHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return reversedHead;
}

如果你严格要求完全不创建任何辅助方法，也可以把反转逻辑内联到合并方法里，但代码会变得臃肿且可读性差，完全没必要——这个方案已经是最优解，逻辑清晰、效率拉满，也是面试中最常被认可的写法。

关于你的可行方案 #

如果你的方案是类似“合并降序+反转”的思路，那完全没问题，这就是最优解；如果是其他思路，可以对比上面的两种方式看看效率和可读性。

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