[리트코드] 21. Merge Two Sorted Lists

# 문제 설명

2개의 정렬된 연결리스트인 list1, list2가 주어진다. 2개의 연결리스트를 하나의 정렬된 연결리스트로 합쳐라.

 

# 입출력 예시

입력	출력
1 -> 2 -> 4 1 -> 3 -> 4	1 -> 1 -> 2 -> 3 -> 4 -> 4

 

# 코드 풀이

# 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]:
        # l2 연결 : l1 끝났거나 || l2 있는데 l1이 더 크면
        if (not list1) or (list2 and list1.val > list2.val):
            list1, list2 = list2, list1
        
        if list1: # l1 있으면 (우선)
            list1.next = self.mergeTwoLists(list1.next, list2) # 정방향
        return list1

 

정렬된 2개의 연결리스트를 입력받아 정렬된 1개의 연결리스트를 반환하는 문제다.

따라서 입력으로 주어진 연결리스트를 이용하여 풀 수 있다. 주어진 2개의 연결리스트 중 하나를 메인으로 하고, 나머지를 전환하여 풀 수 있다. 

 

위 코드 상에서는 list1을 메인으로 하였다.

항상 노드가 가장 작은 값을 선택해야 한다. 따라서 list2가 list1 더 크다면 둘을 바꾸어 준다.

 

 

어려웠던 부분.

가장 작은 노드부터 시작해서, 더 큰 노드를 하나씩 뒤에 연결하는 알고리즘으로 풀었었다.

하지만 이런 방식으로 풀면 결국 가장 마지막 노드만 남게 된다. 따라서 처음 노드를 반환해야 하는 문제를 마주한다.

 

이는 함수의 재귀호출을 통해 해결할 수 있다.

결과적으로 함수가 반환해야 하는 것은 가장 처음의 메인노드이고, 그 다음의 노드는 메인이 되는 list1의 다음노드를 인수로 재귀호출하여 list1.next에 붙여주면 된다.

 

 

# 핵심 포인트

 

- 입력으로 주어진 데이터가 정렬된 연결리스트이고, 마찬가지로 정렬된 연결리스트를 반환하므로 입력 데이터를 활용해야 한다.

- 순서대로 노드를 연결하여 노드를 연결하면, 연결리스트의 특성 상 마지막 노드만이 남는다. 이를 해결하기 위해 함수의 재귀호출을 활용하여 해결할 수 있다.