单链表反转

给定单向列表：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9，反转后的链表为：1 ← 2 ← 3 ← 4 ← 5 ← 6 ← 7 ← 8 ← 9，这里 → 表示左指向右，← 表示右指向左。

代码实现（kotlin编写）：

/**
 * 链表数据结构
 */
class Node constructor(val data: Char) {
    var next: Node? = null

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append(data)
        var tmp: Node? = next
        while (tmp != null) {
            sb.append(tmp.data)
            tmp = tmp.next
        }
        return sb.toString()
    }
}

//为了测试方便，将字符转换为链表来存储
fun toLinkedListStr(str: String?): Node? {
    if (str.isNullOrEmpty())
        return null
    var head: Node? = null
    var next: Node? = null
    for (ch in str) {
        val node = Node(ch)
        next?.next = node
        next = node
        if (head == null) {
            head = node
            next = node
        }
    }
    return head
}

/**
 * 单向链表反转
 */
fun reverse(head: Node?): Node? {
    head ?: return null
    head?.next ?: return head

    var tmp: Node? = null
    var curr = head
    while (curr?.next != null) {
        var next = curr.next
        curr.next = tmp
        tmp = curr
        curr = next
    }
    curr?.next = tmp
    return curr
}

fun main() {
    val str1 = toLinkedListStr("123456789")
    println("$str1 反转后：${reverse(str1)}")
}

测试结果为：

123456789 反转后：987654321