[알고리즘] Merge Two Sorted Lists(LeetCode) - Swift

문제 링크

Merge Two Sorted Lists - LeetCode

접근 방법

결과값 linked list를 만들고, 마지막 노드값을 가지고 있는 노드를 하나 생성합니다.

두 노드를 비교하면서 더 작은 값을 가지고 있는 노드를 추가하고, 한 노드를 다 병합했다면 나머지 노드를 뒤에 이어줍니다.

풀이

class Solution {
    func addList(_ list: ListNode?, _ currentPos: ListNode?, _ addValue: Int) -> (ListNode?, ListNode?) {
        var list = list
        var currentPos = currentPos
        
        if list == nil {
            list = ListNode(addValue)
            currentPos = list
        } else {
            currentPos?.next = ListNode(addValue)
            currentPos = currentPos?.next
        }
        
        return (list, currentPos)
    }
    
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        var result: ListNode?
        var currentPosition: ListNode? = result
        
        var node1: ListNode? = list1
        var node2: ListNode? = list2

        while node1 != nil && node2 != nil {
            if let val1 = node1?.val, let val2 = node2?.val {
                if val1 < val2 {
                    (result, currentPosition) = addList(result, currentPosition, val1)
                    node1 = node1?.next
                } else {
                    (result, currentPosition) = addList(result, currentPosition, val2)
                    node2 = node2?.next
                }
            }
            
        }
        
        if node1 == nil {
            if result == nil {
                result = node2
            } else {
                currentPosition?.next = node2
            }
        } else {
             if result == nil {
                result = node1
            } else {
                currentPosition?.next = node1
            }
        }
        
        return result
    }
}