P66_3.kt

package ch17

import datatype.ListNode

class P66_3 {
    fun insertionSortList(head: ListNode?): ListNode? {
        // 코틀린은 함수의 파라미터를 수정할 수 없기 때문에 별도의 변수로 선언
        var node = head
        // 루트를 가리키는 변수 선언, 나중에 parent.next를 결과로 리턴
        val parent = ListNode()
        // 정렬을 끝낸 대상을 가리키는 포인터
        var p = parent

        // 다음 노드가 없을 때 까지 끝까지 순회
        while (node != null) {
            // 정렬을 끝낸 포인터(p)의 다음 값이 정렬을 해야 할 대상(head)보다 작다면 계속 이동
            while (p.next != null && p.next.`val` < node.`val`)
                p = p.next

            // 서로 위치를 교환하고 정렬을 해야할 대상(head)은 다음 노드로 이동
            val pNext = p.next
            val headNext = node.next
            p.next = node
            node.next = pNext
            node = headNext
            // 정렬을 끝낸 포인터(p)의 값이 다음번 정렬을 해야 할 대상(head)보다 클때만 포인터 맨 앞으로 이동
            if (node != null && p.`val` > node.`val`)
                p = parent
        }
        return parent.next
    }
}