[리트코드] Merge Two Sorted Lists(python)

리트코드, Merge Two Sorted Lists_정렬된 두 개의 리스트 병합

 

TL;DR

• 연결 리스트(Linked list)를 문제 조건에 맞게 구현할 수 있는지

문제 분석

1. 두 개의 정렬된 리스트를 병합하고, 정렬된 리스트의 형태로 반환한다.
2. 반환되는 리스트는 주어진 두 개의 함께 리스트를 엮어(splicing) 만들어야 한다.

 

- 1 : 해결해야 하는 문제에 대해서 말하고 있다.

- 2 : 반환 조건에 대해서 말하고 있다. 별도의 연결 리스트를 선언하지 않고, 두 개의 연결 리스트를 하나의 정렬된 연결 리스트로 만들어야 한다.

입출력 형태

입출력 예시

 

- 예시에는 배열처럼 주어졌지만 실제로는 연결 리스트로 구현되어 있다.

- 두 개의 연결 리스트를 예시 1과 같이 오름차순으로 정렬된 하나의 연결 리스트로 반환해야 한다.

풀이

class Solution:        
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # recursive
        if (not l1) or (l2 and (l1.val >= l2.val)): # 1
            l1, l2 = l2, l1
            
        if l1: # 2
            l1.next = self.mergeTwoLists(l1.next, l2)
            
        return l1

 

- 재귀적인 호출 방법으로 문제를 해결할 수 있다.

- 1 : 주어진 연결 리스트 L1과 L2의 첫 번째 노드의 값을 비교하여, 더 작은 값을 가진 연결 리스트를 L1으로, 나머지를 L2로 서로 바꾼다.(swap). 이 때, L1과 L2가 None이면 비교할 대상이 없으므로 None이 아님을 조건에 비교 이전에 명시해야 한다.

- 2 : L1이 None이 아니라면 L1의 next에 올 연결 리스트를 재귀적인 호출을 통해 연결한다.

    - 함수에서는 L1과 L2의 val을 비교하여 L1에는 더 작은 값을 가진 연결 리스트를 할당한다. 이 과정이 반복되면 값이 작은 순서대로 재귀 함수에서 return되어 정렬된 상태로 연결 리스트가 연결되게 된다.

- 최종적으로 L1을 반환한다.