Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

아니 풀고보니 솔루션이 유료됐네...

아무튼 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        
        results = []
        def listToArray(listNode: ListNode):
            results.append(listNode.val)
            if not listNode.next:
                return
            listToArray(listNode.next)
            
        listToArray(list1)
        listToArray(list2)
            
        results.sort()
        
        resultList = ListNode(results[0])
        results.pop(0)
        def arrayToList(results, resultList):
            if not results:
                return
            item = results.pop(0)
            resultList.next = ListNode(item)
            arrayToList(results, resultList.next)
        arrayToList(results, resultList)
        return resultList

대충 설명하자면,
2개의 링크드리스트를 돌면서 하나의 리스트에 모두 추가한다
그 다음 sort 함수를 불러서 리스트를 정렬
정렬한 리스트를 돌면서 링크드리스트로 변경했다

다 풀고보니 너무 무식하게 풀 것 같기도하고 sort를 쓰면 애초에 이 문제의 의도와 다른 것 같아서 다시 풀어봤다

문제의 의도는 하나의 링크드리스트에 다른 링크드리스트를 연결하는 방식으로 풀어라는것 같아서 아래와 같이 풀었다

# 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 list1:
            return list2
        if not list2:
            return list1
        
        def merge(node1, node2, beforeNode):
            if not node1 and not node2:
                return
            if not node1 and node2:
                beforeNode.next = ListNode(node2.val)
                merge(node1, node2.next, beforeNode.next)  
            elif not node2 and node1:
                beforeNode.next = ListNode(node1.val)
                merge(node1.next, node2, beforeNode.next)
            elif node1.val > node2.val:
                beforeNode.next = ListNode(node2.val)
                merge(node1, node2.next, beforeNode.next)
            elif node1.val <= node2.val:
                beforeNode.next = ListNode(node1.val)
                merge(node1.next, node2, beforeNode.next)
            
        result = None
        if list1.val >= list2.val:
            result = ListNode(list2.val)
            merge(list1, list2.next, result)
        else:
            result = ListNode(list1.val)
            merge(list1.next, list2, result)
            
        return result

다시 풀고보니 광적으로 None 예외처리를 해놨는데
전반적으로 뭔가 if문 떡칠해두고
문제 의도대로 링크드리스트 2개를 merge했지만
불필요하게 새로 링크드리스트를 만들어서 노드도 새로 생성하다보니 메모리 낭비도 발생했다

다만 파이썬이다보니 기본적으로 주소 참조라서 기존의 링크드리스트에 어떻게 끼워넣어야되지를 몰랐는데
다른 사람들의 답을 보니 역시 너무 멍청하게 풀었다...

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head=ListNode(-1)
        cursor=head
        
        while l1!=None and l2!=None:
            if l1.val <= l2.val:
                cursor.next=l1 
                l1=l1.next 
            else:
                cursor.next=l2 
                l2=l2.next
            
            cursor=cursor.next 
        
        if l1!=None:
            cursor.next=l1
        else:
            cursor.next=l2
            
        return head.next

중간에 cursor.next=l1, l1=l1.next 이렇게하면 메모리참조를 끊을 수 있었는데
풀면서 이렇게 짜면 l1이 l1.next로 overwrite되서 사라질거다라고 생각해서 무식하게 짰던것 같다

아무튼 결과는 아래와 같다(역순)

메모리는 큰 차이는 없었지만 런타임에서 약간의 차이가 있었다

상위권은 아니지만 중위권으로 일단 만족을 ㅎㅎ

맨 위가 다른 분의 정답(역순)