21. 合并两个有序链表

# 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]:
'''
遍历链表然后排序串起来
'''
lis = []
while list1:
lis.append(list1.val)
list1 = list1.next
while list2:
lis.append(list2.val)
list2 = list2.next
lis.sort()
head = ListNode() # 虚头
a = head
for i in lis:
a.next = ListNode(i)
a = a.next
return head.next