题解 | #牛群编号的回文顺序#

知识点：快慢指针，反转链表

解题思路：

先快慢指针找到终点，再反转之后的链表，之后在从头和中点向后遍历，比较是否相等

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return bool布尔型
 */
func isPalindrome(head *ListNode) bool {
	// write code here
	if head == nil {
		return true
	}
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	pre, cur, next := (*ListNode)(nil), slow.Next, slow.Next
	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre, cur = cur, next
	}
	left, right := head, pre
	for right != nil {
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}
	return true
}