將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        ret_l=[]
        if l1 is None or l2 is None:
            if l1 is None :
                return l2
            else:
                return l1
        else:
                    
            
            while 1:
                if l1.next and l2.next:
                    ret_l.append(l1.val)
                    ret_l.append(l2.val)
                    l1=l1.next
                    l2=l2.next
                elif l1.next:
                    ret_l.append(l1.val)
                    l1=l1.next
                elif l2.next:
                    ret_l.append(l2.val)
                    l2=l2.next
                else:
                    if l1.next==None:
                        ret_l.append(l1.val)
                    if l2.next==None:
                        ret_l.append(l2.val)
                    break
        ret_l.sort()
        
        ret_node=""
        
        for i in range(0,len(ret_l)):
            if i ==0:
                ret_node=ListNode(ret_l[0])
                cur_node=ret_node
            else:
                
                new_node=ListNode(ret_l[i])
                cur_node.next=new_node
                cur_node=cur_node.next
        return ret_node