[자료 구조/알고리즘] 단일 연결 리스트 - 구현

class ListNode(
    var value: Int
) {
    val next: ListNode? = null

    fun createSingleLinkedList(values: List<Int>): ListNode? {
        val head = ListNode(values[0])
        var current: ListNode? = head

        for (i in 1 until values.size) {
            current?.next = ListNode(values[i])
            current = current?.next
        }

        return head
    }

    fun printSingleLinkedList(head: ListNode?) {
        var current = head
        while (true) {
            current = current?.next ?: return
            println(current?.value)
        }
    }
}

fun main() {
    val values = listOf(1, 2, 3, 4, 5)
    val singleLinkedList = createSingleLinkedList(values)
}

fun mergeTwoSingleLinkedList(l1: ListNode?, l2: ListNode?) {
    // 현재 노드에 대한 참조 변수이다. 연걸 리스트의 모든 노드를 참조하게 된다.
    var list1 = list1
    var list2 = list2

    if (list1 == null) return list2
    if (list2 == null) return list1

    // 헤드 노드의 참조를 그대로 유지하는 노드 변수이다.
    val head = ListNode(0)
    // 새로운 연결 리스트를 만들어나가기 위한 노드 변수이다.
    var current: ListNode? = head

    // 연결 리스트1과 연결 리스트2의 모든 노드를 탐색한다.
    // 두 연결 리스트에 대해 현재 노드가 null이 아닌 경우 탐색을 계속 수행한다.
    // 하나라도 null인 경우 탐색을 종료한다.
    while (list1 != null && list2 != null) {
        // 각 노드를 비교하여 작은 노드를 새로운 연결 리스트의 노드로 추가한다.
        if (list1.`val` <= list2.`val`) {
            current?.next = list1
            // 노드 참조를 그다음 노드로 변경한다.
            list1 = list1.next
        } else {
            current?.next = list2
            list2 = list2.next
        }
        current = current?.next
    }

    // 마지막 노드를 처리한다.
    // null이 아닌 노드를 마지막 노드로 연결한다.
    current?.next = list1 ?: list2

    return head.next
}