[leetcode 21] Merge Two Sorted Lists

21. Merge Two Sorted Lists

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

해결 과정

시작 기준이 되는 head ListNode와 현재 노드를 가리키는 current ListNode를 할당한다.

입력으로 들어온 l1과 l2의 값을 확인하며, currnet.next 에 둘 중 작은 값을 갖는 ListNode를 넣는다. (l1과 l2가 둘다 null이 아닐때 까지)

마지막으로, l1이 null이면 l2를, l2가 null이면 l2을 current.next에 넣는다.

head.next에 시작 노드가 있기 때문에 head.next를 반환한다.

코드

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    val head = ListNode(-1)
    var current = head
    
    var l1 = l1
    var l2 = l2
        
    while(l1 != null && l2 != null) {
        if(l1.`val` > l2.`val`) {
            current.next = l2
            l2 = l2.next
        } else {
            current.next = l1
            l1 = l1.next
        }
        current = current.next
    }
        
    if(l1 == null) {
        current.next = l2
    } else if(l2 == null) {
        current.next = l1
    }

    return head.next
}

배운 점

• 노드와 노드들을 잇는 선들의 그림을 그리고, 이를 끊고 이어보며 문제를 푸는 방법이 도움이 되었다.

• 재귀를 활용해서도 풀 수 있다.

  • 탈출조건: l1 == null 또는 l2 == null
  • 반환되는 ListNode가 result

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    if(l1 == null) return l2
    if(l2 == null) return l1
        
    if(l1.`val` > l2.`val`) {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    } else {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    }
}