21. Merge Two Sorted Lists

두 개의 연결리스트를 합치는데, 크기 순으로 합치는 문제

 

[1,3,4], [1,2,3] <- 배열처럼 썼지만 실제로는 연결리스트임 (1->3->4, 1->2->3)

답은 1->1->2->3->3->4이다. 

 

책에는 다른 방법이지만, 알아보기 힘들어서 풀어서 생각을 했다. 

각 연결리스트를 하나의 리스트에 넣고, 정렬을 한다. 이후에 다시 연결 리스트로 만들어서 출력한다. 

 

문제에서 주어진 시간복잡도나 공간복잡도의 제약사항이 없어 가능한 위 방법이 가능했던것 같다. 

 

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = []
        if not l1 and not l2:
            return None
        while l1:
            result.append(l1.val)
            l1 = l1.next
        while l2:
            result.append(l2.val)
            l2 = l2.next
        result.sort()
        head = res = ListNode(-1)
        for item in result:
            res.next = ListNode(item)
            res = res.next
        return head.next

위에 배열로 변환하는 방식은 효율성이 떨어진다. 반복문을 2번 돌려야하는 번거로움도 있다. 

 

책에 나와 있는 재귀 호출 풀이에 대해서 설명해보자. 

l1의 첫번째 값과 l2의 첫번째 값을 비교하고, 작은 값을 l1의 next에 이어가는 방식이다. 

    def mergeTwoLists(self, l1, l2):
        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

l1 : [1->2->4], l2: [1->3->4]가 초기값이다. 

 

처음에는 1번 조건에 만족하지 않고, 2번에 만족하게 된다.

[2->4], [1->3->4] 로 재귀 호출

 

1번에 의해서 l1과 l2를 swap한다. 

[1->3->4], [2->4]로 바뀌게 되고 2번에 의해서 결과가 1->1이 된다.

[3->4], [2->4]로 재귀 호출

 

1번에 의해서 값을 스왑하고, [2->4], [3->4]가 된다. 

l1.next에 재귀호출 [4], [3->4]를 인자로 전달한다.

 

1번에 의해서 [3->4], [4]가 되고 1->1->2->3이 된다. 

[4], [4]를 인자로 넣고 호출한다. 

 

[4],[4]가 남아있을때 값이 같으므로 1번에 만족하지 않고, 

2번을 만족하게 되는데, 기존 l1에 4가 연결되어 있고, l2를 마지막으로 연결한다. 

 

코드가 짧아서 이해하기 어려운데(사실 책 그림도 어렵다)

손으로 그려보면 쉽게 이해가 된다.