[ LeetCode ] 21 Merge Two Sorted Lists

📌 Problem

주어진 2개의 정렬된 연결 리스트를 하나의 정렬된 연결 리스트로 병합하여 반환하면 된다. 이 때 연결 리스트는 언어에서 제공하는 연결 리스트(Java나 Kotlin에서는 LinkedLIst) 클래스가 아니라 주석에 표현되어 있는 연결 리스트를 사용한다.

📌 Solution

LinkedList collection
만약 언어에서 제공하는 연결 리스트를 사용했다면 굉장히 쉽게 구현이 가능했을 것이다.

val listA = LinkedList<Int>().apply { (1..10 step 2).forEach { add(it) } }
val listB = LinkedList<Int>().apply { (2..10 step 2).forEach { add(it) } }
val list = listA.plus(listB).sorted()
println("list = $list")
// list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

하지만 직접 제공한 연결 리스트를 사용하기 때문에 구현 방법을 생각해야 한다. 그렇다고 크게 어렵지는 않다. 각각의 list에 있는 node를 차례대로 탐색하면서 더 작은 값을 가진 node를 결과 리스트에 우선 삽입하면 된다.

ans는 0을 값으로 가진 결과 리스트이다. 이후 반환을 할 때는 두 번째 node부터 반환을 한다.

node는 현재 정답 리스트에 마지막으로 삽입된 node이다. 해당 node에 다음 값을 연결하면 된다.

nodeA와 nodeB는 각각 list1과 list2의 미탐색 node 중 가장 앞 node이다. Node를 탐색하면 다음 node으로 바꾸면 된다.

val ans = ListNode(0)

var node: ListNode? = ans
var nodeA = list1
var nodeB = list2

Node 탐색 과정
Node 탐색 과정은 다음과 같다. 둘 다 null이 아니면 두 node를 비교하여 작은 값을 삽입하며 이를 반복한다.

while (nodeA != null && nodeB != null) {
    if (nodeA.`val` < nodeB.`val`) {
        node!!.next = ListNode(nodeA.`val`)
        nodeA = nodeA.next
    } else {
        node!!.next = ListNode(nodeB.`val`)
        nodeB = nodeB.next
    }
    node = node.next
}

둘 중 하나가 null이 되면 더 이상의 비교는 무의미하다. null이 아닌 쪽 전체를 삽입하면 된다.

if (nodeA != null) node!!.next = nodeA
else node!!.next = nodeB

📌 Code

fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
    val ans = ListNode(0)

    var node: ListNode? = ans
    var nodeA = list1
    var nodeB = list2

    while (nodeA != null && nodeB != null) {
        if (nodeA.`val` < nodeB.`val`) {
            node!!.next = ListNode(nodeA.`val`)
            nodeA = nodeA.next
        } else {
            node!!.next = ListNode(nodeB.`val`)
            nodeB = nodeB.next
        }
        node = node.next
    }

    if (nodeA != null) node!!.next = nodeA
    else node!!.next = nodeB

    return ans.next
}