问题描述
Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
问题分析
问题需要我们在O(N)的时间和O(1)的空间复杂度内解决。所以基本前提是单链表只遍历一次。
如果不是回文单链表，而是判断回文字符串，那么常见做法是定义2个指针，分别指向一头一尾，向中间移动，判断扫过的字符是否相等即可。那么对于单链表，思想类似，只不过手段上要变换一下。
单链表只能由一个方向进行遍历，因此双指针方式不可行，那么我们就考虑先找到单链表的中间位置，然后从中间位置分别向2边遍历，判断对应元素是否相等。所以找到中间位置后，我们需要对其中一半的单链表进行翻转，然后再遍历。
综上，我们采取如下方式进行：
- 利用快慢指针找到单链表的中间位置
- 在步骤1的过程中，对慢指针扫过的部分进行单链表翻转
- 在找到中间位置后，左半部分已经翻转完毕，此时左右各自向两边顺序遍历，判断对应元素是否一致即可。
示例代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// O(N)时间 O(1)空间
// 1. 利用快慢指针找到单链表的中间位置
// 2. 在1过程中，对慢指针扫过的部分进行单链表翻转
// 3. 找到中间位置后，从中间各自向两边遍历，判断是否一致
func isPalindrome(head *ListNode) bool {
ans := true
if head == nil || head.Next == nil {
return ans
}
// 如果仅有2个元素，直接判断即可
if head.Next.Next == nil {
return head.Val == head.Next.Val
}
// 定义快慢指针slow, fast; 以及用来进行单链表翻转的辅助指针prev, next
slow, fast, prev, next := head, head, head, head.Next
for {
if fast.Next == nil || fast.Next.Next == nil {
break
}
fast = fast.Next.Next
// 如果prev指针为head，将prev.Next置为nil，防止后面遍历时出现环导致空指针引用
if prev == head {
prev.Next = nil
}
// 快慢指针移动，同时进行单链表翻转
prev = slow
slow = next
next = next.Next
slow.Next = prev
}
// 如果fast.Next为nil，说明单链表元素个数为奇数；此时slow位于中间元素，需要往前挪一个位置再与next指向的右半部分进行比较
if fast.Next == nil {
slow = slow.Next
}
for {
if slow == nil {
break
}
if slow.Val != next.Val {
return false
}
slow = slow.Next
next = next.Next
}
return true
}