leetcode-21

21. 合并两个有序链表

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

示例1：

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

示例2：

输入：l1 = [], l2 = [0]
输出：[0]

官方解法（迭代)：

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

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

def mergeTwoLists2(self, l1: ListNode, l2:ListNode) -> ListNode:
    if l1 == None and l2 == None:
        return ListNode()
    elif l1 != None and l2 == None:
        return l1
    elif l1 == None and l2 != None:
        return l2
    else:
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists2(l1.next,l2) # 在l1的后面插入l2 
            return l1
        else:
            l2.next = self.mergeTwoLists2(l2.next,l1) # 在l2的后面插入l1
            return l2

解法：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None and l2 == None:
            return None
        elif l1 != None and l2 == None:
            return l1
        elif l1 == None and l2 != None:
            return l2
        if l1.val < l2.val:
            res = ListNode(l1.val)
            l1 = l1.next
        else:
            res = ListNode(l2.val)
            l2 = l2.next
        
        
        p = res
        # 遍历
        while l1 or l2:
            if l1 == None and l2 != None:
                p.next = l2
                break
            elif l2 == None and l1 != None:
                p.next = l1
                break
            else:        
                # print("++")
                if l1.val < l2.val:
                    p.next = ListNode(l1.val) # 链接
                    p = p.next # 指向尾部
                    l1 = l1.next
                else:
                    p.next = ListNode(l2.val)
                    p = p.next
                    l2 = l2.next  
        return res

一种更优雅的解法：

def mergeTwoLists2(self, l1: ListNode, l2: ListNode) -> ListNode:
    if not l1 or not l2:
        return l1 if l1 else l2
    
    head = ListNode()
    tail = head
    aPtr = l1
    bPtr = l2

    while aPtr and bPtr:
        if aPtr.val < bPtr.val:
            tail.next = aPtr.next
            aPtr = aPtr.next
        else:
            tail.next = bPtr.next
            bPtr = bPtr.next
        tail = tail.next
    tail.next = aPtr if aPtr else bPtr
    return head.next