LeetCode - The World's Leading Online Programming Learning Platform

하나하나 붙이는 방법

문제 풀이 아이디어

가장 직관적인 방법이다. 그냥 새로운 링크드리스트를 하나 만들고 l1과 l2를 완전탐색해서 새로운 링크드리스트의 node로 추가해나가는 것이다.

이 방법의 단점은 head를 따로 저장해두어야 하기 때문에 변수가 늘어나서 코드가 깔끔하게 나오지 않는 다음 점이다. 하지만 코드 자체는 매우 직관적으로 보면 바로 무슨 말인지 알 수 있다.

코드

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        // 노드를 새로운 링크드 리스트로 옮기는 함수
            // reference를 그대로 가져와야 하니 때문에 inout을 사용한다.
        func moveNodeToAns(list: inout ListNode?) {
            now?.next = list
            now = now?.next
            list = list?.next
        }
        
        var list1 = list1
        var list2 = list2
        
        // 새로운 링크드리스트
            // head를 따로 저장해두어야 한다. (나중에 거슬러 올라올 수 없기 때문에)
        var now: ListNode? = nil
        var head: ListNode? = nil
        
        // 새로운 리스트의 head를 정하는 과정
            // l1와 l2의 현재 head의 val 중에 낮은 값
        let first1 = list1?.val ?? 101
        let first2 = list2?.val ?? 101
        
        if first1 < first2 {
            now = list1
            head = list1
            list1 = list1?.next
        } else {
            now = list2
            head = list2
            list2 = list2?.next
        }
        
        // l1, l2의 리스트 중 어느 하나의 리스트를 완전 탐색할 때까지 작은 node들 부터 새 리스트에 연결한다.
        while let val1 = list1?.val, let val2 = list2?.val {
            if val1 < val2 {
                moveNodeToAns(list: &list1)
            } else {
                moveNodeToAns(list: &list2)
            }
        }
        
        // 남은 node들을 연결한다.
        now?.next = list1 == nil ? list2 : list1
        
        return head
    }
}

재귀함수를 활용하는 방법

문제 풀이 아이디어

위 풀이는 문제를 풀 수는 있고 문제에서 원하는 동작을 곧이곧대로 순서대로 구현하기 때문에 이해하기 좋다는 장점은 있지만 코드가 굉장히 길고 변수를 지나치게 많이 쓰며, 새 리스트의 head를 정하는 과정이 별도로 있는 등 깔끔하지 못한 코드다.

더 깔끔한 방법은 재귀함수를 활용하는 것이다. 아래 그림을 참고해서 설명하도록 하겠다.

재귀함수는 자기 자신을 호출하는 함수이다. 현재 주어진 mergeTwoLists (이하 merge)함수는 l1과 l2를 내림차순으로 합친 리스트의 head를 리천하는 함수이다.. 아직 함수가 실행되기 전 단계인 0단계를 보면 아직 합쳐진 리스트 m은 비어있다. m의 현재 node는 merge함수의 결과 값이 되어야 한다. 그 함수의 결과 값은 m의 현재 node가 되어야 하는 것은 l1과 l2의 현재 node 중에 더 작은 val을 가진 node이다.

merge를 1번 실행해서 1단계가 되었다. 리턴 값이자 l1의 현재 node인 1을 m의 현재 node로 만들었다. 그러면 next인 l1.next가 된다. 그러면 m은 이제 1을 현재 node로 가진 길이1의 링크드리스트가 되었다. 그렇다면 이제 m뒤에 이어지는 리스트는 node를 1칸 이동한 l1과 l2를 merge한 리스트의 head이다. 다시 merge 함수가 그 값을 리턴하도록 한다.

2번째 merge 실행으로 2단계가 되었다. 똑같이 리턴 값인 l2의 head를 m의 다음 node로 만들었다. 같은 원리로 l2의 현재 node는 1칸 이동한 l2.next가 된다. 이제 m의 뒤에 이어질 리스트는 다시 l1, l2를 merge한 리스트의 head가 된다.

이런 원리로 l1혹은 l2가 nil이 될 때까지 (= 마지막 node를 지남) merge 함수를 재귀적으로 실행한다. 재귀함수는 stack에 쌓여서 실행되기 때문에 가장 마지막에 실행된 함수부터 실행되고 m 리스트의 마지막 node 부터 차례로 리턴이 되어 실행된다. 결과적으로 마지막에는 가장 처음에 실행한 merge 함수의 리턴값, 즉 l1과 l2 리스트를 내림차순으로 합친 리스트의 head가 되는 것이다.

코드

class Solution {
    // 최종적으로 merge된 링크드리스트의 head를 리턴하는 재귀함수
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        // l1에 비었으면 l2를 연결, l2가 비었으면 l1을 연결
        if l1 == nil { return l2 }
        if l2 == nil { return l1 }
        
        // l1의 현재 node가 l2의 현재 node 보다 작으면?
        if l1!.val < l2!.val {
            // l1의 현재 node가 head가 되고 뒤에 l1의 나머지 부분과 l2를 merge한 링크드리스트를 붙이면 됨
            l1!.next = mergeTwoLists(l1!.next, l2)
            return l1 // 그리고 그 붙인 링크드리스트의 head를 리턴
        // 반대의 경우는?
        } else {
            // l2의 현재 node가 head가 되고 뒤 에 l2의 나머지 부분과 l1을 merge한 링크드리스트를 붙이면 됨
            l2!.next = mergeTwoLists(l2!.next, l1) // 그리고 그 붙인 링크드리스트의 head를 리턴
            return l2
        }
    }
}

마치며…

재귀함수로 푸는 풀이는 이해만 한다면 아주 명쾌하지만 문제를 처음 보고 떠올리기란 쉽지 않다. merge라는 작업이 작은 부분의 merge 작업들의 합으로 이뤄져있다는 것을 파악할 수 있어야 한다. 꾸준한 연습만이 해결책이 아닐까?