简述Java实现合并两个有序链表 ？

在Java中，你可以通过创建一个新的链表，然后遍历两个有序链表，依次比较每个节点的值，将较小的节点添加到新链表中，从而合并两个有序链表。以下是一个基本的实现方法：

首先，我们定义链表节点的类（假设链表中的元素为整数）：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

然后，我们实现合并两个有序链表的函数：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哑节点作为新链表的头
        ListNode dummy = new ListNode(0);
        // 当前处理的新链表的节点
        ListNode current = dummy;

        // 当两个链表都不为空时，进行遍历
        while (l1 != null && l2 != null) {
            // 如果l1的值小于l2的值，则将l1的节点添加到新链表
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                // 否则，将l2的节点添加到新链表
                current.next = l2;
                l2 = l2.next;
            }
            // 移动新链表的当前节点
            current = current.next;
        }

        // 当l1或l2其中一个链表为空时，将另一个链表的剩余部分直接添加到新链表
        if (l1 != null) {
            current.next = l1;
        }
        if (l2 != null) {
            current.next = l2;
        }

        // 返回新链表的头节点（即哑节点的下一个节点）
        return dummy.next;
    }
}

这个解决方案的时间复杂度是O(n+m)，其中n和m分别是两个输入链表的长度。因为我们需要遍历这两个链表的所有节点。空间复杂度是O(1)，因为我们只使用了常量的额外空间来存储哑节点和当前节点。