通过链表判断字符串是否为回文？

问题：如果一个字符串是通过单向链表来存储的，那么怎么判断该字符串是否为回文字符串？其时间复杂度以及空间复杂度是多少呢？

字符串的回文判断，我们应该都听过，但是这里的要求是通过链表来判断，那么怎样才能保证时间复杂度以及空间复杂度都比较小呢？

首先学习一个链表移动的概念：快慢指针，那么什么是快慢指针呢?
快慢指针指的是，针对同一个链表定义 2 个指针，它俩移动的速度一快一慢。如果我们保持慢指针每次移动 1 步，快指针每次移动2步，在同时遍历一个链表时，当快指针移到链表尾部时，慢指针刚好移动到链表的中间。

快慢指针有什么妙用呢？

1. 在有序链表中寻找中位数
   如果一个有序单向链表为：1 → 2 → 3 → 4 → 5 → 6 →7，我们定义 2 个指针 fast、slow 都从表头 1 开始遍历，fast 指针每次移动 2 步，slow 指针每次移动 1 步，最后当 fast 指针移动到链表尾部 7 时，slow 指针刚好移动到中间的数据 4，这样 slow 指针指向的就是该链表的中位数了。
2. 找到链表中的倒数第 n 个节点
   假设链表长度为 length，倒数第 n 个节点即正数第 length - n + 1 个节点。同样定义 2 个指针 fast、slow，都指向链表头部，fast指针先向后移动 n - 1 步，接着同时移动 fast、slow 指针，保持速度一致，当 fast 指针移动到链表尾部时，slow 指针指向的就是链表的倒数第 n 个节点数据了。
   例如链表：1 → 2 → 3 → 4 → 5 → 6 →7，需要找到倒数第 3 个节点，这里是节点 5，正数就是第 7 - 3 + 1 = 5 个节点。fast、slow 一开始都指向表头 1，先将 fast 指针向后移动 3 - 1 = 2 步到达节点 3 ，接着同时移动 fast、slow 指针，每次移动速度都一致，当 fast 指针移动到链表尾部 7 时，slow 指针刚好移动到节点 5，节点 5 刚好就是该链表的倒数第 3 个节点了。

解决方案

回到开头这个题目上来，那么我们怎么通过链表来判断字符串是否回文呢？思路如下：

1. 通过快慢指针定位到中位节点；
2. 在遍历链表的同时，将中位节点前面的链表逆序；
3. 将中位节点前后两部分的字符进行逐一比较，判断是否回文；
4. 恢复逆序部分的链表；

代码如下（采用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 isPalindrom(head: Node?): Boolean {
    head ?: return false
    head.next ?: return true
    var fast: Node? = head          //快指针
    var middle: Node? = head        //慢指针，用来定位中间数据的指针
    var reversed: Node? = null      //前半部分的逆序指针
    while (fast?.next != null) {
        fast = fast?.next?.next
        //开始逆序前半部分指针
        var next = middle?.next
        middle?.next = reversed
        reversed = middle
        middle = next
    }

    //临时变量，为了后面恢复链表
    var tmp1 = reversed
    var tmp2 = middle

    //到此，其实整个链表被分成了2个链表，middle指针表示后半部分的数据，reverse表示前半部分的数据
    //假设原来字符串链表为：a → b → c → d → c → b → a
    //那么现在链表其实断开成2个了：
    //   1、reversed：前半部分逆序链表，a ← b ← c（注意指针方向）
    //   2、middle：后半部分链表，d → c → b → a

    //如果快指针不为空，则表示链表有奇数个，慢指针刚好指向中间的数据
    if (fast != null) {
        //中间数据指针往后移一个，后半部分刚好与逆序部分的数据个数相同了
        middle = middle?.next
    }

    var result = true
    //现在只需对 middle、reversed 这2个链表遍历访问比较即可了
    while (middle != null) {
        if (middle?.data != reversed?.data) {
            result = false
            break
        }
        middle = middle?.next
        reversed = reversed?.next
    }

    //为了不影响原来链表的数据，我们需要将断开的链表恢复成原样
    while (tmp1 != null) {
        var next = tmp1?.next
        tmp1.next = tmp2
        tmp2 = tmp1
        tmp1 = next
    }
    return result
}

fun main() {
    val str1 = toLinkedListStr("abba")!!
    val str2 = toLinkedListStr("aabbccddddccbbaa")
    val str3 = toLinkedListStr("sdsldfjksdf")

    println("$str1 是否回文字符串：${isPalindrom(str1)}")
    println("$str2 是否回文字符串：${isPalindrom(str2)}")
    println("$str3 是否回文字符串：${isPalindrom(str3)}")
}

测试结果如下：

abba 是否回文字符串：true
aabbccddddccbbaa 是否回文字符串：true
sdsldfjksdf 是否回文字符串：false

时间复杂度为：O(n)
空间复杂度为：O(1)

题外话：可能有人会想，我们再用一个数组来存储每个字符，然后遍历数组来比较岂不是更简单。确实如此，但这样做的时间复杂度为 O(n)，空间复杂度也为 O(n)了。