LeetCode.234 回文链表

题目描述：

234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

请判断一个链表是否为回文链表。

示例一

输入: 1->2
输出: false

示例二

输入: 1->2->2->1
输出: true

提示：

• 链表中节点数目在范围[1,105][1, 10^5][1,105] 内
• 0 <= Node.val <= 9

进阶： 你能否用 O(n)O(n)O(n) 时间复杂度和 O(1)O(1)O(1) 空间复杂度解决此题？

思路分析

双指针法

什么是回文，"上海自来水来自海上"

这可是小学时代的顺口溜了，我们那会怎么判断的，正过来和倒过来一样的呗，或者一个从头数，一个从末尾数，每一步都是一样的结果应该，所以落到这算法里，我们就可以定义2个指针，一个从头开始遍历，另一个从末尾开始遍历。

但是这里有个问题，链表的实现一般是通过节点关联下一个节点的方式实现的，所以我们从头往后遍历没问题，但是反过来，复杂度就高了。

怎么解决呢，用数组，数组双指针遍历是非常容易的

所以现在我们分两步

第一步，将值复制到数组中

第二步，双指针遍历数组来判断

AC代码

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val vals =  ArrayList<Int>()


        var currentNode = head
        while(currentNode != null) {
            vals.add(currentNode.`val`)
            currentNode = currentNode?.next
        }

        var head = 0
        var tail = vals.lastIndex
        while(head < tail) {
            if(vals.get(head) != vals.get(tail)) {
                return false
            }
            head++
            tail--
        }
        return true

    }
}

总结

这个解法算是基础，题解中还有递归和快慢指针的解法，需要再了解。

参考

回文链表 - 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

我的快慢指针都从头开始，感觉更好理解 - 回文链表 - 力扣（LeetCode） (leetcode-cn.com)