[LeetCode][Python3] 21. Merge Two Sorted Lists

풀이 1

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ary=[]
        while l1 or l2:
            if l1:
                ary.append(l1.val)
                l1=l1.next
            elif l2:
                ary.append(l2.val)
                l2=l2.next
        ary.sort()
        if len(ary)>0:
            l3=ListNode(ary[0],None)
            itr = l3
            for i in ary[1:]:
                node = ListNode(i,None)
                itr.next=node
                itr=itr.next
            return l3
        return None

 

ary.sort()

을 통해 정렬을 할 수 있지만 이는 알고리즘 공부에 도움이 되지 않는다고 생각했다.

 

풀이 2

# 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: ListNode, l2: ListNode) -> ListNode:
        idx1=0
        idx2=0
        ary=[]

        while(l1 and l2):
            if(l1.val<l2.val):
                ary.append(l1.val)
                l1=l1.next
            else:
                ary.append(l2.val)
                l2=l2.next
        if(l1==None):
            while(l2):
                ary.append(l2.val)
                l2=l2.next
        if(l2==None):
            while(l1):
                ary.append(l1.val)
                l1=l1.next
        if(len(ary)==0): return None
        l3=ListNode(ary[0])
        itr=l3
        for i in ary[1:]:
            node = ListNode(i)
            itr.next=node
            itr=itr.next
        return l3