21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
给定两个已经排好序的链表的头部，然后按序合并。足后返回合并的list。

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

思考

由于无法在最初的时候判断链表的长度，只能默认往list1里面添加元素。使用类似双指针的概念，第一个指针对应着list1所遍历的位置，第二个指针对应着list2的遍历位置。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not bool(list1):
            return list2
        elif not bool(list2):
            return list1
        
        head = ListNode(0, list1)
        p1 = head.next
        pre_p1 = head
        p2 = list2
        
        while bool(p1) and bool(p2):
            t1 = p1.val
            t2 = p2.val
            
            if t1>=t2:
                pre_p1.next = p2
                pre_p1 = p2
                tmp2 = p2.next
                p2.next = p1
                p2 = tmp2
            else:
                pre_p1 = p1
                p1 = p1.next
                
        if bool(p1):
            return head.next
        else:
            pre_p1.next = p2
            return head.next

写了很长时间才写了一道题。真的有点麻了。这道题其实不难，但是就是很多细节没有掌握，得重新复盘。我希望这种情况会随着刷题的题数增加而解决。

答案解析

递归

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

利用递归算法，思路和我差不多，但是把我的循环变成了递归，瞬间高级感就上来了。
时间和空间复杂度都是n+m。n,m分别为两个链表的长度。

迭代

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prehead = ListNode(-1)

        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 if l1 is not None else l2

        return prehead.next

这个就有点类似暴力破解法了，创建另一个链表，每次判断大小然后放入链表内，最后返回。
这么一看我的方法好像是他们两个的结合体。。。

总结

对于细节的把握还不是很好。

每次想起来美国站的解题不能看，国内站的可以看就觉得很好玩。还是国内好啊。