[Q. 14] 두 정렬 리스트의 병합

정렬되어 있는 두 연결 리스트를 합쳐라.

 

연결 리스트의 정의는 앞의 문제와 같다. 여기서 리스트는 작은 숫자 순으로 정렬되어 있다. 이런 2리스트를 합치기 위해 여러 방법이 있지만 책에서는 재귀를 이용한 방법으로 깔끔하게 풀어 이를 구현하여 보았다.

# 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 (not list1) or (list2 and list2.val < list1.val):
            list2, list1 = list1, list2
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)

        return list1

 

먼저 재귀로 들어가기 전, list1이 없거나 list1의 값이 list2의 값보다 클 때는 두 리스트의 위치를 변경해준다.

그 다음, list1이 있을 때 까지 list1의 다음 값을 mergeTwoLists(list1.next, list2)로 설정해준다.

예를들어 1->2->4, 1->3->4 두 연결 리스트가 있다고 생각해보자.

1. list1 값이 1이 list2의 값 1보다 큰게 아니므로 list1.next 는 mergeTwoLists(2->4, 1->3->4)가 된다.

2. list1의 값 2가 list2의 값 1보다 커서 두 리스트의 위치는 변경되고 list1.next는 mergeTwoLists(3->4, 2->4)가 된다.

3. list1의 값 3이 list2의 값 2보다 커서 두 리스트의 위치는 변경되고 list1.next는 mergeTwoLists(4, 3->4)가 된다.

4. list1의 값 4가 list2의 값 3보다 커서 두 리스트의 위치는 변경되고 list1.next는 mergeTwoLists(4, 4)가 된다.

5. list1의 값 4가 list2의 값 4보자 큰게 아니므로 list1.next는 mergetTwoLists(None, 4)가 된다.

6. list1의 값이 없으므로 두 리스트의 위치는 변경되고 list1.next는 mergeTwoLists(None, None)이 된다.

7. 이제 list1이 리턴된다.

 

이를 마지막 mergeTwoList 함수가 실행된 시점부터 보면 다음과 같다.

1. None

2. 4->None

3. 4->4->None

...

7. 1->1->2->3->4->4->None인 연결리스트가 리턴된다.