合并两个有序链表

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

示例 ：

分析

初步思考

这种题目好像也没什么技巧可言。

将两个链表最小的头节点作为新的链表，比较原有两个链表的头节点的值，新的链表去连接小的头节点，依次接下去，直到两个链表为空。

     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;
        }
    }
​
    public 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 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;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }
    prev.next = list1 == null ? list2 : list1;
    return prehead.next;
}

这种方法，我们取消了递归的方式，只用了一个新的链表就可以实现了,时间复杂度上也没有影响。

复杂度

• 时间复杂度：O ( n + m)。我们遍历得最坏得情况下，次数最多就是两个链表得长度之和。有一个链表仅剩最后一个元素且比另一个链表都大，那么你不得不比较完所有元素，才能结束。
• 空间复杂度：O(1)。我们仅仅增加了一个新的链表。

总结

使用递归的代码可读性确实非常好，但是对时间复杂度和空间复杂度的影响比较大。所以如果递归层数无法确定的情况，建议还是不要使用递归。我们知道我们每个进程的栈容量是有限的，递归层次过多或者边界条件没把握好，很容易导致栈溢出。递归的空间消耗往往比非递归要消耗的多很多，建议慎用递归。有些情况使用递归确实代码可读性更好，思路更清晰，使用的时候也可以在满足需求的情况下对深度进行限制来防止栈溢出。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！