[파이썬 알고리즘] 두 정렬 연결 리스트의 병합

두 정렬 리스트의 병합

리트코드로 플러가기

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

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

---

code: mergeTwoLinkedLists.py

재귀 구조 활용

두 연결 리스트가 정렬되어 있기 때문에, 두 연결 리스트의 첫 값부터 차례대로 비교하며 리턴하면 되는 문제이다.

먼저, l1 과 l2의 값을 비교하여 현재 노드의 값이 작은 쪽이 l1이 되도록 스왑한다.

그 후, l1 노드의 next값이 그 다음 재귀에서 return 된 노드가 되도록 하면 모든 재귀문이 호출되고 난 뒤의 l1이 답의 첫 노드가 된다.

def mergeTwoLists(self, l1, l2):
    # 1. l1이 None이면, l1과 l2를 무조건 바꾸어야 함
    # 2. 이때, l2가 None이면 바꾸면 안됨
    # 3. l1, l2 노드의 값이 작은 쪽이 l1가 됨
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1

    # 이렇게 바꾸었을 때, l1이 None이면 l1, l2둘다 None임
    # 둘다 None이라면 재귀를 더이상 하면 안되기에, if로 체크함
    if l1:
        # l1이 존재하면, l1의 next를 찾기 위한 재귀를 실행
        l1.next = mergeTwoLists(l1.next, l2)

    return l1

위 코드의 주석과 같은 순서로 코드는 실행되게 된다.

순차적 붙여넣기

좀더 직관적으로 재귀를 이용하지 않고, 두 연결 리스트를 차례로 탐색하며 새 ListNode에 붙여넣는 풀이도 있다.

좀 더 직관적이나, 공간 복잡도는 올라가게 된다.

    def mergeTwoLists(self, l1, l2):
        result = ListNode()
        current = result

        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next

        if l1:
            current.next = l1

        elif l2:
            current.next = l2

        return result.next

링크드 리스트를 조작할 때, 위 코드의 current와 같이 참조를 만들어 두고 참조에서 로직을 실행한 뒤, 결과를 리턴하게 하는 방법을 볼 수 있다.