思路

这道题是要咱们将两个有序的链表有序的合并起来，需要注意的是，这两个链表都是有序的，既然是有序的就好办多了，咱们不妨用两个指针，一个在 l1 链表的头部，另一个在 l2 链表的头部，然后相互比较，小的那个放在前面，这时另一个问题来了，小的那个节点放在哪里？其实咱们可以虚拟一个伪头节点，然后将每次比较的结果都放到这个伪头节点后面。

其中 0 为 伪头节点。
过程整理：

• 先去判断一个 l1 和 l2 是否为空，如果一方为空，那么直接返回另一发就行。
• 创建一个伪头节点。
• 通过两个指针，分别指向 l1 和 l2 的头部，进行比较，小的放到 伪头节点的后面，指针向后移动，直到 l1 或 l2 没有节点了。
• 最后，判断l1 或 l2 还有谁没有遍历完，直接接到伪头节点的链表最后。

AC代码

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        // 创建伪头节点
        ListNode node = new ListNode(0);
        ListNode cur = node;
        // 当 l1 和 l2 都不为空
        while (l1 != null && l2 != null) {
            // 如果l2 值小于 l1
            if (l1.val > l2.val) {
                // 将 l2 加入到结果链表的后面
                cur.next = l2;
                // 指针向后移动
                l2 = l2.next;
            } else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        // 判断 l1 或 l2 谁还有剩余
        if (l1 != null) {
            cur.next = l1;
        } else if (l2 != null) {
            cur.next = l2;
        }

        return node.next;
    }

时间复杂度：O(m+n), m 和 n 为两个链表的节点数。
空间复杂度：O(m+n), m 和 n 为两个链表的节点数

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。