【数据结构与算法】【LeetCode】【链表】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, l1, l2):
        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
def createLink(lista):
    head = ListNode(1)
    rear =head
    for i in range(1,len(lista)):
        new = ListNode(lista[i])
        rear.next=new
        rear = new
    return head

if __name__=="__main__":
    a=[1,2,4]
    b=[1,3,4]
    l1=createLink(a)
    l2=createLink(b)
    #l1=ListNode(1,ListNode(2,ListNode(4)))
    #l2=ListNode(1,ListNode(3,ListNode(4)))
    a1 = Solution()
    p=a1.mergeTwoLists(l1,l2)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def mergeTwoLists(self, l1, l2):
        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

def createLink(lista):
    head = ListNode(1)
    rear =head
    for i in range(1,len(lista)):
        new = ListNode(lista[i])
        rear.next=new
        rear = new
    return head

if __name__=="__main__":
    a=[1,2,4]
    b=[1,3,4]
    l1=createLink(a)
    l2=createLink(b)
    #l1=ListNode(1,ListNode(2,ListNode(4)))
    #l2=ListNode(1,ListNode(3,ListNode(4)))
    a1 = Solution()
    p=a1.mergeTwoLists(l1,l2)
    list1=[]
    while(p!=None):
        list1.append(p.val)
        #print(p.val)
        p=p.next
    print(list1)