[LEETCODE] 21: Merge Two Sorted Lists(Python)

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
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

list1과 list2를 비교해 더 작은 값을 head로 삼는다. head를 만들 리스트의 기준으로 삼고 순회한다. list1, list2는 각각 기존 리스트 방향을 가리켜야 한다.

1. list1, list2 의 val값을 비교하여 더 작은 노드를 head로 둔다. list1과 list2 중 head가 된 값은 자신의 next 노드로 이동한다. first라는 임시 노드는 head를 가리키도록 한다.
2. 아래 과정을 무한 반복한다.
   1. 만약 list1, list2 중 하나가 None이라면 None이 아닌 나머지를 head에 연결한 뒤 무한 루프를 빠져나온다.
   2. list1, list2의 val값을 비교해 작은 값을 head.next로 연결한다.
   3. head를 head.next로 이동시킨다.
   4. list1이 더 작았다면 list1=list1.next으로 둔다. list2도 동일하게 처리한다.
3. 위 과정이 끝났다면 통합 리스트의 첫 노드를 가리키던 first를 반환한다.

예외로 둘 다 빈 리스트라면 빈 리스트를 반환한다. 둘 중 하나가 None이라면 None이 아닌 나머지 리스트를 반환한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1==None and list2==None:
            return None
        elif list1==None:
            return list2
        elif list2==None:
            return list1
        
        if list1.val<=list2.val:
            head=list1
            list1=list1.next
        else:
            head=list2
            list2=list2.next
        first=head
        
        while True:    
            if list1==None:
                head.next=list2
                break
            elif list2==None:
                head.next=list1
                break
                
            if list1.val<=list2.val:
                head.next=list1
                head=head.next
                list1=list1.next
            else:
                head.next=list2
                head=head.next
                list2=list2.next
                
        return first

시간복잡도

두 리스트를 순회하면서 새 리스트를 작성하므로 O(2*n)이다.