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

• 리스트를 단일 연결 리스트로 변환

    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
    }