[Leetcode]21. Merge Two Sorted Lists

알고리즘 시간에 배웠던 합병정렬의 반복적 기법으로 문제를 해결했다. 책을 보니 재귀를 이용한 방법이 있었다.

 

 

배운점

• 무조건 헤드에 값을 넣으려고 하지말자 어차피 return head.next 로 해결할 수 있다.
• 연결리스트를 이어줄 때 어차피 끝까지 순회하면서 수정되니까 따로 값만 전달할 필요없이 바로 리스트 값을 저장해주어도 문제되지않는다.
• 파이썬에서 비어있을 때는 not명령어를 이용한다.

반복적 풀이

def mergeTwoLists2(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 and not l2:
            return None

        head = temp = ListNode()
        while l1 and l2:
            if l1.val <= l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next

        if l1 or l2:
            temp.next = l1 or l2

        return head.next

재귀적 풀이

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or (l2 and l1.val > l2.val):
            l1 , l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next,l2)
        return l1