LeetCode，判断一个链表是否为回文链表
力扣题目：
请判断一个链表是否为回文链表。
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/palindrome-linked-list/
解题
1. 将值复制到数组中后用双指针法
- 我们首先遍历链表，将链表中的值（Val）保存到一个数组中
- 然后对数组进行遍历，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。
- 每移动一步就比较一次值，如果值不相等，说明不是回文链表。
如下 Go 实现的解法：
func isPalindrome(head *ListNode) bool {
s := []int{}
for ; head != nil; head = head.Next {
s = append(s, head.Val)
}
l := len(s)
for k, v := range s[:l/2] {
if v != s[l-1-k] {
return false
}
}
return true
}
空间复杂度：O(n)，这种解法，我们使用了一个数组列表存放链表的元素值。n 指的是链表的元素个数。
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
2. 快慢指针
我们可以将链表的后半部分进行反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们再将链表恢复原样。虽然不需要恢复也能通过测试用例。
整个流程可以分为以下五个步骤：
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
步骤 1 我们使用「快慢指针」在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
//找到前半部分链表的尾节点
endNode := end(head)
//翻转后半部分链表
fanNode := fan(endNode.Next)
//判断是否回文
n1 := head
n2 := fanNode
for n2 != nil {
if n1.Val != n2.Val {
return false
break
}
n1 = n1.Next
n2 = n2.Next
}
endNode.Next = fan(fanNode)
return true
}
func end (head *ListNode) *ListNode{
fast := head
slow := head
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func fan(head *ListNode) *ListNode{
var pre, cur *ListNode = nil, head
for cur != nil {
tmpNode := cur.Next
cur.Next = pre
pre = cur
cur = tmpNode
}
return pre
}
「复杂度分析」
- 时间复杂度：O(n)，其中 n 是链表的大小。
- 空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-08-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
