题解 | #判断一个链表是否为回文结构#

package main

import . "nc_tools"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类 the head
 * @return bool布尔型
 */
func isPail(head *ListNode) bool {
	// 直接返回
	if head == nil || head.Next == nil {
		return true
	}
	// 如何能快速对比前后呢
	// 而且需要判断两个数字是否能构成回文串？
	// 1. 先找到链表的中点
	// 2. 中点以后得链表进行翻转
	// 3. 对比是否能构成回文
	length := 0
	newHead := head
	for newHead != nil {
		length++
		newHead = newHead.Next
	}
	mid := (length + 1) / 2
	midHead := head
	// 找到中点
	for mid > 0 {
		midHead = midHead.Next
		mid--
	}
	flag := true
	isPailTwolist(head, midHead, &flag)

	return flag

}

// 判断两个链表，头尾是否能构成回文
func isPailTwolist(left *ListNode, right *ListNode, flag *bool) {
	if right == nil {
		return
	}
	isPailTwolist(left, right.Next, flag)
	// log.Println("left:", left.Val, "right:", right.Val)
	*flag = *flag && (left.Val == right.Val)
	// 直接修改指向的内容，但是方法比较trick
	left.Val = left.Next.Val
	left.Next = left.Next.Next
}