LeetCode 21. Merge Two Sorted Lists

두 개의 LinkedList가 있는데 이 두 개를 하나로 합쳐서 정렬하는 문제이다.

풀이

나의 풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None
        elif not list1 or not list2:
            return list2 or list1
        else:
            answer = temp = ListNode(0)
            while list1 and list2:
                if list1.val < list2.val:
                    temp.next = list1
                    list1 = list1.next
                else:
                    temp.next = list2
                    list2 = list2.next
                temp = temp.next

            if list1:
                temp.next = list1
            else:
                temp.next = list2

        return answer.next

가장 처음에 list1과 list2가 None일 경우를 판단하고 return 해준다.

정답으로 사용할 LinkedList(answer)를 만들어야 하는데, 이때 answer는 head로 사용해야 하기 때문에 temp를 하나 더 만들어 준다.

그다음부터는 while문을 사용하여 list1과 list2의 node들의 크기를 비교하면서 순서대로 temp.next에 node를 삽입해 준다.

 

여기서 나는 마지막 if문을 작성하지 않아서 계속 오류가 났었는데, while문에서 list1과 list2가 먼저 끝나는 경우를 생각해서 마지막 if 문을 사용해 남은 node들을 temp에 삽입해줘야 한다.

 

그리고 마지막으로 head로 사용한 answer.next를 return 해주면 끝이다.

결과값1

살짝 다른 풀이

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # if not list1 and not list2:
        #     return None
        # elif not list1 or not list2:
        #     return list2 or list1
        # else:
            answer = temp = ListNode(0)
            while list1 and list2:
                if list1.val < list2.val:
                    temp.next = list1
                    list1 = list1.next
                else:
                    temp.next = list2
                    list2 = list2.next
                temp = temp.next

            if list1:
                temp.next = list1
            else:
                temp.next = list2

            return answer.next

위 풀이는 list1과 list2가 없을 때를 고려하지 않고 풀이하는 방식이다.

왜 성공하는지는 사실 잘 모르겠으나, 문제없이 성공하고 심지어 runtime도 짧았다.

결과값2