[LeetCode] Algorithms | 21. Merge Two Sorted Lists | Python

Problems

 

항상 Linked List만 나오면 많이 헷갈려서 연습장에 하나하나 그려보고 적어본다.

잘 쓰지 않아서 익숙하지 않아서겠지 이렇게나마 계속 접하면 익숙해지겠지

 

암튼 해야하는 일은 list를 merge하고 순서대로 정렬해야한다.

그냥 python 함수로 extend 하고 sort 때려버리고 싶지만 그래도 한번 차근차근 해보자

 

1. 우선 빈 list1가 빈 list이면, list2로 return 해주고, 그 반대로 list2가 빈 list이면 list1으로 return 해주기

2. while 문을 통해서 빈 list일 때까지 반복해주기

3. ListNode의 val를 가지고와서 크기 비교해주기

   3-1. list1의 val이 더 크다면, 비어있는 ListNode에 list1을 담아주고 list1의 포인터는 다음으로 옮겨주기

   3-2. 반대의 경우엔, list2에 동일하게 적용하기

4. 새로 생성해서 값을 담고 있는 ListNode의 포인터도 다음으로 옮겨주기

5. 하나의 list가 먼저 탐색을 마친다면, 나머지 list를 결과에 담아주기

 

작성한 스크립트는 다음과 같다

# 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 is None:
            return list2
        elif list2 is None:
            return list1

        result = ListNode()
        current = result
        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

            if list1 is None:
                current.next = list2
            elif list2 is None:
                current.next = list1
                
        return result.next

 

성 ~ 공