21 Merged Two Sorted Lists

1. Description

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

Merge the two lists in a 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.

 

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.

2. Algorithms

 값을 비교해서 Sorted List를 만드는 알고리즘은 3가지 입력의 경우의 수를 가진다.

• list1, list2 둘다 none ListNode일 경우
• list1, list2 둘 중 하나만 none ListNode인 경우
• list1, list2 둘다 none ListNode가 아닌 경우

세번째 경우, 값을 비교해서 curr의 ListNode에 값을 순차적으로 넣지만 비교가 끝난 ListNode는 none값을 갖게 되므로 Nonetype .val error를 출력하게 된다. 이때 두번째 경우를 while문 안에 묶어 하나의 ListNode가 종료되더라도 자동으로 값을 추가할 수 있도록 코드를 설계한다.

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

1. list1, list2가 none일 경우 자동으로 output.next(none)을 출력한다
2. while문 안에 list1 혹은 list2가 none일 경우 나머지 ListNode에서 값을 자동으로 추가할 수 있도록 코드를 구성한다.
3. 나머지 경우에 값을 비교하여 ListNode를 추가할 수 있도록 코드를 구성한다.

3. Conclusion

• Code' s Time Compexity : $O(N)$