反转链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

方法一：递归

算法思路：

比较两个链表的头部值，较小的一个节点与剩下元素的merge操作结果合并。

代码实现：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

复杂度分析：

时间复杂度： $O(n + m)$ ，其中 $n$ 和 $m$ 是链表的长度，至多只会递归调用两个链表的每个节点一次。
空间复杂度： $O(n+m)$ ，同上。

方法二：双指针

算法思路：

设置一个哨兵节点prehead，以便最后返回合并后的链表。
维护prev指针，比较l1与l2的节点值，若l1小于l2，则将l1当前节点接在prev后面，同时将l1指针后移一位。对l2同理，如此循环直至l1或l2指向了null。
循环终止时，合并剩余的非空链表。

代码实现：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                prev.next = list1;
                prev = list1;
                list1 = list1.next;
            }else{
                prev.next = list2;
                prev = list2;
                list2 = list2.next;
            }
        }
        prev.next = list1 == null? list2: list1;
        return prehead.next;
    }
}

复杂度分析：

时间复杂度： $O(n+m)$ ，。其中 $n$ 和 $m$ 是链表的长度，while循环的次数不会超过两个链表的长度之和。
空间复杂度： $O(1)$ ，只需要常数的空间存放若干变量。

参考：

合并两个有序链表 - 合并两个有序链表 - 力扣（LeetCode）