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

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
	}
	slow := head
	mid := head.Next
	fast := head.Next.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		mid = mid.Next
		fast = fast.Next.Next
	}
	slow.Next = nil
	//反转
	reserveList := reserve(mid)
	//判断回文
	for head != nil && reserveList != nil {
		if head.Val != reserveList.Val {
			return false
		}
		head = head.Next
		reserveList = reserveList.Next
	}
	return true
}

func reserve(head *ListNode) *ListNode {
	res := &ListNode{Val: 0}
	for head != nil {
		next := head.Next
		head.Next = res.Next
		res.Next = head
		head = next
	}
	return res.Next
}