LeetCode.234 回文链表
站长
· 阅读数 4
题目描述：
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
}
}
总结
这个解法算是基础，题解中还有递归和快慢指针的解法，需要再了解。