package Exercise

import java.util.*

fun main(args: Array<String>) {
    // 不为空
    val root = initLinkList()
    print("未排序之前：")
    print(root)
    println()
    print("排序完之后：")
    print(Solution().sortList(root))
    // 空
    println()
    print("未排序之前：")
    print(null)
    println()
    print("排序完之后：")
    print(Solution().sortList(null))
}

/**
 * 初始化单链表
 *
 * @return 返回单链表
 * */
fun initLinkList(): ListNode? {
    val random = Random()
    val root = ListNode(0, null)
    var temp: ListNode = root
    for (i in 1..10) {
        temp.next = ListNode(random.nextInt(100), null)
        temp = temp.next!!
    }
    return root
}

/**
 * 打印链表
 *
 * @param root 头结点
 * */
fun print(root: ListNode?) {
    if (root == null) return
    var result = root
    while (result != null) {
        print(result.value)
        print(" ")
        result = result.next
    }
}

class ListNode(var value: Int, var next: ListNode?)

class Solution {
    fun sortList(root: ListNode?): ListNode? {
        if (root?.next == null) return root
        var head = root
        // 左链表
        var left = ListNode(0, null)
        val leftHead = left
        // 右链表
        var right = ListNode(0, null)
        val rightHead = right
        // 中间链表
        var mid = ListNode(0, null)
        val midHead = mid
        // 支点的值
        val value = head.value

        /**
         * 快速排序，循环读取每一个链表结点，将其放在三个子链表中
         * */
        while (head != null) {
            when {
            // 如果小于支点，就放在左链表
                head.value < value -> {
                    left.next = head
                    left = head
                }
            // 如果大于支点，就放在右链表
                head.value > value -> {
                    right.next = head
                    right = head
                }
            // 如果等于，就放在中间链表
                else -> {
                    mid.next = head
                    mid = head
                }
            }
            head = head.next
        }

        left.next = null
        right.next = null
        mid.next = null
        return merge(this.sortList(leftHead.next), midHead.next, sortList(rightHead.next))
    }

    /**
     * 合并结点
     *
     * @param left 左结点
     * @param right 右结点
     * @param mid 中间结点
     * @return 返回头部结点
     * */
    private fun merge(left: ListNode?, mid: ListNode?, right: ListNode?): ListNode? {
        val leftTail = getTail(left)
        val midTail = getTail(mid)
        midTail!!.next = right
        return if (leftTail != null) {
            leftTail.next = mid
            left
        } else mid
    }

    /**
     * 获取链表的尾结点
     *
     * @param root 链表的头结点
     * @return 返回链表尾结点
     * */
    private fun getTail(root: ListNode?): ListNode? {
        if (root == null) return root
        var head = root
        while (head!!.next != null) {
            head = head.next
        }
        return head
    }
}