面试题25. 合并两个排序的链表

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

很适合用递归进行求解。
首先判断l1或者l2为空的情况：

1. l1为空的话，把l2剩下的返回就行了。
2. l2为空的话，把l1剩下的返回就行了。
3. 都为空返回空，为了少写一行代码，就返回l1.

上面的既是空的情况的判断，也是递归结束的条件。

代码

如果l1的头结点值比较小，那么这次应该取``，也就是：

mergeHead = l1

剩下l1.next 和l2再进行相同的操作,得到mergeHead的下一个节点:

mergeHead.next = self.mergeTwoLists(l1.next, l2)

省略中间变量mergeHead，合并起来就是我下面完整版的鬼畜模样了。（牺牲了一点可读性，并不是很建议在面试中使用

l1.next = self.mergeTwoLists(l1.next, l2)

最后，两个if 可以用个交换合并。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None: return l2
        if l2 is None: return l1
        if l1.val > l2.val: l1,l2 = l2,l1
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

总结

递归思路。
注意边界。