[leetcode/python] 21번 Merge Two Sorted Lists

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

Merge Two Sorted Lists - LeetCode

 

문제 요약: 정렬된 두 연결 리스트를 하나로 합쳐라(정렬 유지)

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        result = None

        # 예외처리
        if list1 is None and list2 is None:
            return result

	# 초기값 계산
        if list1 and (list2 is None or list1.val < list2.val):
            result =  ListNode(list1.val)
            list1 = list1.next
        else:
            result = ListNode(list2.val)
            list2 = list2.next

        # 병합
        while list1 or list2:

            if list1 and (list2 is None or list1.val < list2.val):
                result.append(list1.val)
                list1 = list1.next
            else:
                result.append(list2.val)
                list2 = list2.next
        
        return result

시간복잡도 : O(n)

 

개선한다면...

1. result에 처음에 아무 값이나 넣어줘서 시작하고, 나중에 result.next 부터 리턴하면 굳이 초기값을 어떤걸 넣어줘야할지 결정할 계산할 필요가 없다.

2. list1이나 list2가 비어있을 경우 때문에 예외처리하느라 코드가 복잡해졌다. 둘 다 모두 있다고 생각하고 비교한 다음에, 비어있지 않은 나머지를 합쳐주면 더 깔끔해진다.

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 임의의 초기값
        result = ListNode(0)

        # 병합
        while list1 and list2:
            if list1.val < list2.val:
                result.append(list1.val)
                list1 = list1.next
            else:
                result.append(list2.val)
                list2 = list2.next
        
        result.tail.next = list1 or list2
        return result.next