[Leetcode/Easy] 두 정렬 리스트의 병합 (21. Merge Two Sorted Lists, Swift)

https://leetcode.com/problems/merge-two-sorted-lists/description/

 

🤔 문제 설명

두 개의 정렬된 연결 리스트 list1과 list2가 주어진다.

이때, 처음 두 연결 리스트의 노드를 서로 연결하여 하나의 연결 리스트로 만들어라 (병합해라).

list1 = [1,2,4], list2 = [1,3,4]
// [1,1,2,3,4,4]

 

💡 풀이

단순하게 두 연결 리스트가 모두 nil이 아닐 때까지는 각 연결 리스트의 앞 값을 기반으로 비교하고, 둘 중 더 작은 값을 반환할 병합 리스트에 연결하고, (연결해줄 병합 리스트와 + 사용한 연결 리스트를) 한 칸 전진시키는 방식으로 단순하게 연결해나가면 된다.

둘 중 하나의 연결 리스트가 nil이 되는 순간 (혹은 연결 리스트 두 값다 모두 nil이라 반복 조차 돌지 않았던 경우) nil이 아닌 연결 리스트를 그저 병합 리스트에 이어 붙여주기만 하면 잔여값을 처리할 수 있었다.

+ 해당 로직을 그대로 사용해서 재귀 (Recursion) 방식으로도 문제를 풀 수 있다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 4ms (Beats 90.48%), Memory : 15.68MB (Beats 26.65%)

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {

        let mergeList: ListNode = ListNode(0)
        var moveList: ListNode? = mergeList
        var list1: ListNode? = list1
        var list2: ListNode? = list2

        // 두 리스트 중 하나가 nil이 되기 전까지는 서로 비교하면서 연결
        while (list1 != nil && list2 != nil) {
            guard let unwrapList1 = list1, let unwrapList2 = list2 else { break }  

            // 값 비교해서 더 작은 값을 먼저 연결
            if (unwrapList1.val < unwrapList2.val) {
                moveList!.next = unwrapList1
                list1 = unwrapList1.next
            } else {
                moveList!.next = unwrapList2
                list2 = unwrapList2.next
            }
            moveList = moveList!.next
        }

        // 두 리스트 중 하나 이상이 nil이 된 상황에서는 그냥 뒤에 이어붙이기
        moveList!.next = (list1 == nil) ? list2 : list1

        return mergeList.next
    }
}