请求提供Java原地合并两个有序链表的递归及迭代实现代码

没问题，这就给你整理Java环境下原地合并两个有序链表的两种实现——递归版和迭代版，都是严格的原地操作（只修改节点的next指针，不额外创建新的链表节点）：

思路 #

递归的核心是把大问题拆成重复的小问题：每次比较两个链表的当前头节点，选择值较小的那个作为合并后链表的当前节点，然后递归地合并这个节点的next与剩下的链表部分，直到其中一个链表为空，直接返回另一个链表即可。全程都是原地修改指针，没有额外开辟空间。

代码实现 #

// 首先定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class MergeSortedLists {
    // 递归原地合并方法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 边界条件：如果其中一个链表为空，直接返回另一个链表
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        
        // 比较当前头节点，选择较小的那个，然后递归合并剩下的部分
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

思路 #

迭代版本我们用一个**哑节点（Dummy Node）**来简化边界处理（不用纠结哪个链表作为头节点），然后用一个current指针跟着合并后的链表走：每次比较list1和list2的当前节点，把值较小的那个接在current.next，然后移动对应的链表指针和current指针；当其中一个链表遍历完后，直接把剩下的链表接在current后面即可。全程都是原地修改指针，空间复杂度为O(1)。

代码实现 #

// 同样使用上面定义的ListNode类
public class MergeSortedLists {
    // 迭代原地合并方法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建哑节点，方便后续操作
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // 遍历两个链表，直到其中一个为空
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            // 移动current指针到下一个位置
            current = current.next;
        }
        
        // 把剩下的非空链表接上去
        current.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;
    }
}

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