[21. Merge Two Sorted Lists] (알고리즘)

Linked List

문제

문제 링크

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = [] Output: []

Example 3:

Input: list1 = [], list2 = [0] Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

스스로 고민

접근법

• 두개의 리스트를 비교해서 가장 낮은 수 부터 쌓기

의사코드

• head 를 초기화 한다.
• result 를 설정한다.
• 반복문을 통해 list1 과 list2가 None 값이 아니라면 다음 조건문 검사
• list2 값이 list1 값보다 크거나 같을 경우 result 값의 next 값을 list1 의 값을 업데이트 그 후 list1은 next 값으로 업데이트
• 반대의 경우는 list2에 적용
• list1 의 값이 None 값이 아니라면 result next 값은 list1 값 반대의 경우 list2 값으로 업데이트

구현 코드

class Solution:

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        head = ListNode(-1)

        result = head

        while list1 != None and list2 != None:

            if list1.val <= list2.val:

                result.next= list1

                list1 = list1.next

            else:

                result.next=list2

                list2 = list2.next

            result = result.next

        # Last node  

        if list1!=None:

            result.next=list1

        else:

            result.next=list2

        return head.next

시간 복잡도와 공간 복잡도

시간 복잡도:

• 두 연결 리스트의 모든 노드를 한 번씩 탐색하면서 합치므로, 각 연결 리스트의 길이가 각각 m과 n일 때 시간 복잡도는 O(m + n) 다.

공간 복잡도:

• 추가적인 공간을 할당하지 않고 기존 노드들을 재사용하므로, 추가적인 공간을 사용하지 않아 공간 복잡도는 O(1) 다.

회고 과정

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        curr = d =ListNode()
        while list1 and list2:
            if list1.val<list2.val:
                curr.next=list1
                list1,curr=list1.next,list1
            else:
                curr.next=list2
                list2,curr=list2.next,list2
        if list1 or list2:
            curr.next=list1 if list1 else list2
        return d.next

• 조건문의 경우 다음과 같이 사용하면 좀 더 간결하게 사용 가능하다.
• list1 과 list2 둘 중에 하나가 none 이 아니라면 조건문이 진행되게 만들었다.
• next 값도 조건문으로 들어가게 만들어 졌기 때문에 매우 효율적이라고 생각했다.